【贪心算法】之 K 次取反后最大化的数组和

读完题目以后，我们就应该尽可能地转所有负数，这样才会使sum最大；

刚开始思路是这样子的：

• 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小

• 第二步：从前向后遍历，遇到负数将其变为正数，同时K–

• 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完

• 第四步：求和

  然后遇到的问题就是 怎么按照绝对值大小求和呢？我试着用冒泡排序求了一次，idea可以运行，但是leetcode上超时了；

  换一个思路：

  • 排序，利用Arrays.sort();直接排序；这样子所有可能的负数都会在最前面

  • 从前向后遍历，遇到负数将其变为正数，同时K–；直接求此时数组的和；

  • 循环结束，对数组再次排序；

  • 判断k是否有剩余：

    1.没有剩余，说明此时负数能变正都变正了；此时已经是最大和，返回sum；

    2.如果k有剩，说明负数已经全部转正；

    ? ①此时如果k还剩偶数个就自己抵消掉，不用删减；

    ? ②如果k还剩奇数个就减掉2倍最小正数。 k有剩余，则数组里面都是正数；

public class leetcode_1005 {
    public static void main(String[] args) {
        int[] nums = {-1, -2, 3, -6, 0};
        int k = 2;
        System.out.println(largestSumAfterKNegations(nums, k));
    }

    public static int largestSumAfterKNegations(int[] nums, int k) {
        // 1.排序，从小到大排 有负数就在最前面
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 2.从前向后遍历，遇到负数将其变为正数，同时K--
            if (nums[i] < 0 && k > 0) {
                nums[i] =-nums[i];
                k--;
            }
            //此时全部求和
            sum += nums[i];
        }
        //3.再对数组进行一次排序 此时不管如何nums[0]绝对值都是最小的
        Arrays.sort(nums);
        // 如果k没剩，那说明能转的负数都转正了，已经是最大和，返回sum
        // 如果k有剩，说明负数已经全部转正，所以如果k还剩偶数个就自己抵消掉，不用删减；
        // 如果k还剩奇数个就减掉2倍最小正数。 k有剩余，则数组里面都是正数
        return sum - (k % 2 == 0 ? 0 : 2 * nums[0]);
    }
}