想要精通算法和SQL的成长之路 - K次取反后最大化的数组和

前言

想要精通算法和SQL的成长之路 - 系列导航

一. K次取反后最大化的数组和

原题链接

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

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

1.1 错误的做法

那么这题也是一个贪心思想：

• 尽可能的保持正数不要改变，如果k=0那最好。
• 优先把负数取反，负数越小越好。
• 如果负数全部取反了，k依旧>0怎么办?那只能对正数取反呀，越小越好。

那么对于上面而言，越小越好，那不就是要对数组排序嘛：

Arrays.sort(nums);
1

那么第一反应：

1. 排序完，从前到后遍历，将前面的数字尽管取反即可。同时k减1。
2. 一旦k<=0的时候，后面的数字尽管加就好了。

那么不难得出代码如下：

public int largestSumAfterKNegations(int[] nums, int k) {
   // 排序
   Arrays.sort(nums);
   int count = 0;
   for (int i = 0; i < nums.length; i++) {
       if (k <= 0) {
           count += nums[i];
           continue;
       }
       count += -nums[i];
       k--;
   }
   return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

但是这样是错的：

仔细想想为啥？题目里面有一句话：可以多次选择同一个下标 i ，芜湖，那破案了。我们的程序写出来之后，每个元素只遍历了一次。

那么上面的一个测试案例，正确的做法是：

1. -1这个元素反转一次。
2. 0这个元素反转两次。最终结果1+2+3+0=6。

1.1 正确的做法

1. 我们累加数组元素的时候，应该优先加入绝对值大的数字。因此我们不能从小到大排序，应该根据绝对值来从大到小排序。
2. 遍历过程中，遇到负数，反转一次。
3. 遍历完之后，如果k还是>0，那么就取绝对值最小的数字，也就是排序后的最后一个数字。将其反转n在这里插入代码片次，直到k==0。
4. 最后一次性统计值即可。

代码如下：

public int largestSumAfterKNegations(int[] nums, int k) {
    // 排序
    nums = Arrays
            .stream(nums)
            .boxed()
            .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
            .mapToInt(Integer::intValue)
            .toArray();
    int len = nums.length;
    // 优先先把负数转换
    for (int i = 0; i < len; i++) {
        if (nums[i] < 0 && k > 0) {
            nums[i] = -nums[i];
            k--;
        }
    }
    // 如果k是偶数，那么反转两次还是本身，因此如果为奇数，反转一次即可
    if (k % 2 == 1) {
        nums[len - 1] = -nums[len - 1];
    }
    // 统计累加
    return Arrays.stream(nums).sum();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

知识点：

1. sorted()函数：sorted自定义排序的话，需要操作面向对象类，因此int类型需要转化为Integer类型。
2. boxed()函数：就相当于把int转为Integer。