1005. Maximize Sum Of Array After K Negations #

题目 #

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
- 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。

思路 #

模拟 #

按照数组中负数个数 numNeg 与 k 之间的大小关系进行讨论
- numNeg >= k, 翻转最小的 k 个负数
- numNeg < k 且 k - numNeg 为偶数, 则将所有负数翻转
- numNeg < k 且 k - numNeg 为奇数, 则等同于 k = numNeg + 1 的情况
  - 若minPos为0, 则可以将负号吸收
  - 比较 minPos 和 -maxNeg 的相对大小

代码 #

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int numNeg = 0, maxNeg = Integer.MIN_VALUE, minPos = Integer.MAX_VALUE, sum = 0;
        for (int num: nums) {
            sum += num;
            if (num < 0) {
                numNeg++;
                maxNeg = Math.max(maxNeg, num);
            }
            else if (num < minPos) minPos = num;
        }
        if (numNeg >= k) {
            for (int i = 0; i < k; i++) sum -= 2 * nums[i];
            return sum;
        }
        else {
            if ((k - numNeg) % 2 == 0) {
                for (int i = 0; i < numNeg; i++) sum -= 2 * nums[i];
                return sum;
            }
            else if (minPos == 0) {
                for (int i = 0; i < numNeg; i++) {
                    sum -= 2 * nums[i];
                }
                return sum;
            }
            else {
                for (int i = 0; i < numNeg; i++) {
                    sum -= 2 * nums[i];
                }
                return maxNeg == Integer.MAX_VALUE || -minPos > maxNeg ? sum - 2 * minPos : sum + 2 * maxNeg;
            }
        }
    }
}

致谢 #

宫水三叶