85、★贪心-LeetCode-1005.K次取反后最大化

题目描述：

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

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

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

来源：力扣（LeetCode）

思路：

排序很重要！当然还要学习手写排序和搜索！

贪心体现在：每次：反转最小的负数；反转最小的正数；

代码：

1）错误的情况：忽略了负数取反后会出现小于原来最小正数的情况！

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);//排序：很重要的处理！
        int num = 0;
        for(int i = 0;i < nums.length;i++){
            if(k != 0 && nums[i] < 0){
                nums[i] = -nums[i];//最大负数优先变正
                k--;
            }
            else if(k != 0 && nums[i] >= 0){//只改变一个值
                while(k != 0){//用一个值，把k消耗完
                    nums[i] = -nums[i];
                    k--;
                }
            }
            num += nums[i];
        }
        return num;
    }
}

 2）正确情况！

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);//排序：很重要的处理！
        int num = 0;
        for(int i = 0;i < nums.length;i++){
            if(k != 0 && nums[i] < 0){
                nums[i] = -nums[i];//最大负数优先变正
                k--;
            }
            //全剩正的了，或者k用完了
            num += nums[i];
        }
        Arrays.sort(nums);
        return k % 2 > 0 ? num - 2 * nums[0] : num;
    }
}

用一个值记录了 最小正数内容：避免二次排序

class Solution {
    public int largestSumAfterKNegations(int[] nums, int K) {
        if (nums.length == 1) return K % 2 == 0 ? nums[0] : -nums[0];
        Arrays.sort(nums);
        int sum = 0;
        int idx = 0;
        //这个for用来改值！
        for (int i = 0; i < K; i++) {
            if (i < nums.length - 1 && nums[idx] < 0) {
                nums[idx] = -nums[idx];
                if (nums[idx] >= Math.abs(nums[idx + 1])) idx++;
                continue;
            }
            nums[idx] = -nums[idx];
        }

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return sum;
    }
}