题目描述

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

求解思路

暴力求解法

• 先对nums进行排序；
• 只需要将最小的元素取反，这样对于整个数组的和来讲代价是最小的；
• 在每次将最小的数取负后对数组重新排序；
• 下次再操作数组最小值；
• 如此重复k次。

贪心算法

• 首先对数组进行排序；
• 现将排到数组前面的负数进行取负操作；
• 然后再次对数组进行排序；
• 下面判断k的次数是偶数还是奇数，都是对于操纵最小的一个数组元素而言的；
• 如果为偶数则说明没有变化，如果是奇数，则需要把最小的元素也就是nums[0]取负；
• 最后通过遍历求出数组nums的各元素之和。

输入输出示例

代码

暴力求解法

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        for(int i = 0; i < k; i++){
            nums[0] = (-1) * nums[0];
            Arrays.sort(nums);
        }
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += nums[i];
        }
        return sum;
    }
}

贪心算法

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        for(int i = 0; i < n && nums[i] < 0 && k >0; i++){
            nums[i] = -nums[i];
            k--;
        }
        Arrays.sort(nums);
        if(k % 2 != 0){
            nums[0] = -nums[0];
        }
        int sum = 0;
        for(int i : nums){
            sum += i;
        }
        return sum;
    }
}