贪心算法---1005.K 次取反后最大化的数组和

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

示例 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]

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

- 第一步：将数组按照绝对值大小从大到小排序，**注意要按照绝对值的大小**
- 第二步：从前向后遍历，遇到负数将其变为正数，同时K--
- 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
- 第四步：求和
  然后遇到的问题就是 怎么按照绝对值大小求和呢？我试着用冒泡排序求了一次，idea可以运行，但是leetcode上超时了；

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

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

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

• 判断k是否有剩余：

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

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

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

  ​ ②如果k还剩奇数个就减掉2倍最小正数。 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]);
    }