LeetCode_ 1005_ Maximized array sum after K negations

Topic link

• https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/

Title Description

Give you an array of integers nums And an integer k , Modify the array as follows ：

Select a subscript i And will nums[i] Replace with -nums[i] .
Repeating this process happens to k Time . You can select the same subscript multiple times i.

After modifying the array in this way , Returns an array of The maximum possible and .

Example 1：

 Input ：nums = [4,2,3], k = 1
 Output ：5
 explain ： Select subscript  1 ,nums  Turn into  [4,-2,3] .

Example 2：

 Input ：nums = [3,-1,0,2], k = 3
 Output ：6
 explain ： Select subscript  (1, 2, 2) ,nums  Turn into  [3,1,0,2] .

Example 3：

 Input ：nums = [2,-3,-1,5,-4], k = 2
 Output ：13
 explain ： Select subscript  (1, 4) ,nums  Turn into  [2,3,-1,5,4] .

Tips ：

• 1 <= nums.length <= 10^4
• -100 <= nums[i] <= 100
• 1 <= k <= 104

Their thinking

The law of greed

• Sort the array before each inversion , Just let the smallest take the opposite

AC Code

class Solution {
    
    public int largestSumAfterKNegations(int[] nums, int k) {
    
        int ans = 0;
        for (int i = 0; i < k; i++) {
    
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        for (int num : nums) {
    
            ans += num;
        }
        return ans;
    }
}