1005K次取反后最大化的数组和（贪心）

文章目录 题目[]( leetcode /problems/maximize-sum-of-array-after-k-negations/)算法原理源码总结

题目

如上图，k是取反的次数，在数组【4，-1,3】中，当k = 1，把-2取反为2，和为9；在数组【3，-1，0，2】中，当k = 3，-1取反为1，再把2取反m-k=2次，还是2，和为6.

算法原理

分情况讨论： 设：整个数组中负数的个数是m 个

（1）m>k;把前k小负数，转化为正数（如下图）

（2）m==k,把所有的负数转化成正数（如下图）

（3）m<k;先把所有的负数变成正数；在根据k-m的奇偶性，偶数情况；直接忽略；奇数情况：挑选当前数组中最小的数，变成负数（如下图）。

源码 class Solution { public: int largestSumAfterKNegations(vector<int>& nums, int k) { int m =0,minElem = INT_MAX, n =nums.size(); for(auto x :nums) { if(x < 0) m++; minElem = min(minElem,abs(x));//求绝对值最小的那个数 } //分类讨论 int ret = 0; if(m > k) { sort(nums.begin(),nums.end()); for(int i = 0;i<k;i++) { ret+= -nums[i]; } for(int i = k;i<n;i++) { ret+= nums[i]; } } else { //把所有的负数变成正数 for(auto x :nums) ret+=abs(x); if((k-m) % 2) { ret-=minElem*2; } } return ret; } }; 总结

以上就是1005 K 次取反后最大化的数组和（贪心），喜欢博主写的内容可以一键三连支持博主。