K次取反后最大化的数组和

题目

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）

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

具体思路

1. 先排序；
2. 从前到后遍历，将负数转换成正数； k > 0 时
3. 从前到后遍历，如果记录最小值（注意这个地方不能直接复制 nums[0] ，因为它是负数的话可以直接改变的）
4. 然后如果 **k 有剩余，并且 m o d 2 = 1 ，那么需要修改最后的res **；
5. 返回结果

具体代码

class Solution {
public:
    // 大于就是降序，小于就是升序
    static bool cmp(int a, int b) { return abs(a) > abs(b); }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int res = 0;
        sort(nums.begin(), nums.end(), cmp);
        for (int i = 0; i < nums.size(); i++) {
            // 不能写成
            // if (nums[i] < 0 && k--)
            if (nums[i] < 0 && k) {
                k--;
                nums[i] *= -1;
            }
        }
        // 如果还剩余k，赋值给第一个
        if (k % 2 == 1)
            nums[nums.size() - 1] *= -1;
        for (int i = 0; i < nums.size(); i++) {
            res += nums[i];
        }
        return res;
    }
};

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int res = 0;
        int min = 200;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && k > 0) {
                k--;
                nums[i] = -nums[i];
            }
        }
        for (int i = 0; i < nums.length; i++) {
            res += nums[i];
            min = Math.min(min, nums[i]);
        }
        return k > 0 && k % 2 == 1 ? res - min * 2 : res;
    }
}