Leetcode_99_MaximizeSumOfArrayAfterKNegations

1. question: K次取反后最大化的数组和（简单）

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations

示例 1：

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：

输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

提示：

1 <= nums.length <= 104
-100 <= nums[i] <= 100
1 <= k <= 104

2. answers

这道题的题目描述比较花里胡哨，其实仔细观察，可以发现，就是对数组中的元素进行k次取反操作，可以对某个元素进行多次操作，每次操作都是在上次操作的结果上进行的。求解k次之后的数组和的最大值。

显然，每次对最小数进行操作即可（正数越小，取反之后，也是对结果影响越小；负数越小，取反之后，可以使结果更大），但是不可能每操作一次就进行排序，这样开销太大了。

1. 如果全是正数，排序之后，最左侧是最小值，那么对其取反之后，该值仍然是最小值。所以此时只需对第一个元素进行重复操作即可，无论k有多大，哪怕比数组长度还要大。
2. 如果全是负数，因为负数越小，取反之后越大，所以肯定要排序。如果k小于元素个数，那么直接进行前k个最小元素取反即可。如果k大于元素个数，在将所有元素变为正数之后，对数组排序，转为1的情况。
3. 如果有正有负，首先还是排序，对负数进行情况2操作，最终也可转为情况1。

这三种情况均可认为是情况3。

1. 先排序
2. 找负数的中止下标
3. 对负数进行取反（k–）
4. 判断是否k>0.
5. 对数组排序
6. 如果大于0，每次都对第一个元素进行操作。
7. 求和。

代码如下所示：

public class Solution_0099 {

    public int largestSumAfterKNegations(int[] nums, int k) {

        // 对给定数组升序排列
        Arrays.sort(nums);

        // 找到负数的个数。
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) break;
            else index = i;
        }

        // 对负数进行操作，注意，同时也要小于k。
        for (int i = 0; i <= index; i++) {

            if(k <= 0) break;
            nums[i] = -nums[i];
            k--;
        }

        // 此时，要么是处理完了k次操作，要么是处理完了负数。
        Arrays.sort(nums);

        // 对剩余的数进行操作。
        while(k-- > 0) {
            // 此时，一定是处理完了负数，而还有k。因此上述的排序操作之后，最小值一定是在最左侧且>0，
            // 那么之后，将其取反，变为负数，仍然是最小值，即此时，无论怎么操作，第一个元素一定是最小值。
            // 因此，这里在取反之后，无需再次排序
            nums[0] = -nums[0];
//            Arrays.sort(nums);
        }

        int sums = 0;
        for (int i: nums) {
            sums += i;
        }

        return sums;
    }

    public static void main(String[] args) {
        System.out.println();

//        int[] nums = {4, 2, 3};
//        int k = 1;

//        int[] nums = {3, -1, 0, 2};
//        int k = 3;

        int[] nums = {2, -3, -1, 5, -4};
        int k = 2;

        Solution_0099 s = new Solution_0099();

        System.out.println(s.largestSumAfterKNegations(nums, k));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。