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

发表于： 分类于：
字数： 1376 阅读：≈ 3分钟

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

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）

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

示例

示例 1：

  • 输入：A = [4,2,3], K = 1
  • 输出：5
  • 解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。

示例 2：

  • 输入：A = [3,-1,0,2], K = 3
  • 输出：6
  • 解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。

示例 3：

  • 输入：A = [2,-3,-1,5,-4], K = 2
  • 输出：13
  • 解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。

提示：

  • 1 <= A.length <= 10000
  • 1 <= K <= 10000
  • -100 <= A[i] <= 100

思路

基本思想

对数组反转k次时，尽可能将较大的负数先反转，使得数组中留下的负数越少越好，此时数组相加的和才会更大

主要需要分情况讨论：

  1. k小于负数个数：挑小的负数先反转之后再相加

  2. k大于负数个数：剩下的是奇数，则将最小的的正数反转，剩下的是偶数不用管

    为什么剩下的偶数不用管，因为他可以分成两次两次的反转，由于可以选择任意一个元素，所以分别作用到每个正数上，正->负->正不会产生变化

    但是奇数的话需要注意，两次两次的反转，会剩下一个单次反转，此时只需要挑一个最小的数反转，使其影响最小

    k大于负数个数时需要分情况，正数需要选择真正最小的正数

执行流程

为了将负数集中在一起，并且先反转绝对值较大的负数，我们将元素升序排序，所以绝对值最大的负数会出现在最前面，最小的正数在最后一个负数的后面

遍历数组，遍历的过程中将负数反转，遇到k==0的情况直接退出返回数组求和的结果

遇到正数元素，判断剩下的k是偶数还是奇数，奇数将当前正数元素反转后相加，偶数直接相加

可以想象成此时k全部作用到这个最小的正数上

注意

不要把反转负数和反转正数的代码写在一起，负数反转之后也变成正数，如果放在一起负数会先反转成正数，然后再反转成负数，例如下面的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int sum=0;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();++i){
            //k>0并且元素是负数时才反转
            if(nums[i]<0 && k>0){
                //负变正
                nums[i]=-nums[i];
                --k;
            }
            //负数反转完之后会进入这个地方，并把k置0，导致后面的元素无法反转
            if(nums[i]>0 && k>0){
                if(k%2==1){
                    //正变负
                    nums[i]*=-1;
                    k=0;//直接置0
                }
            }
            //每一个元素都累加
            sum+=nums[i];
        }
        return sum;
    }
};

第一想法是将正数和负数的反转放在一个for循环，这样可以减少代码量，但是负数反转之后也变成了正数，无法区分，所以需要分开

并且普通的按照元素排序，最后一个负数的下一个元素反转之后不一定是最小的正数，例如：[-8,3,-5,-3,-5,-2]，反转之后，最小的正数是2不是3，所以排序时需要按照绝对值排序

容器末尾的元素才是最小的元素

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    //按照绝对值进行排序
    static bool com(int num1,int num2){
        return abs(num1)>abs(num2);
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int sum=0;
        //排序必须按照绝对值降序，这样末尾才是最小的正数
        sort(nums.begin(),nums.end(),com);
        //这个for循环只能负责负数反转
        for(int i=0;i<nums.size();++i){
            //k>0并且元素是负数时才反转
            if(nums[i]<0 && k>0){
                //负变正
                nums[i]=-nums[i];
                --k;
            }
        }
        //k=0无法进入这个if
        if(k%2==1){
            nums[nums.size()-1]=-nums[nums.size()-1];
        }
        //计算累加和
        for(auto num:nums){
            sum+=num;
        }
        return sum;
    }
};

总结

有几个要注意的点：

  1. 对数组排序时只能使用绝对值降序排列：最后一个元素就是全局最小正数
  2. 负数取反和正数取反必须分开：负数取反之后变成正数不好分辨
  3. 负数取反完毕之后如果k大于零，需要判断k的奇偶性，奇数的话作用到正数上会变号