k次取反后最大化的数组和
对数组可以k次取反，可以对一个元素多次取反
当数组中负数的个数大于k，则从小开始对k个取反
当数组中的负数个数为n小于k，先对负数的n个取反。之后重新排序，计算k-n对2取余
当k-n可以整除2，则意味着对一个负数多次操作后还是正的，不影响结果
当k-n不能整除2，一定会最后有一个负数，则对最小的正数取反。
class Solution { public: int largestSumAfterKNegations(vector<int>& nums, int k) { int sum=0; sort(nums.begin(),nums.end()); //判断当前值是负数并且在k个范围内 for(int i=0 ; k>0 && nums[i] <=0 && i<nums.size(); i++,k--) { nums[i] = -nums[i]; } sort(nums.begin(),nums.end()); if(k%2 == 1) nums[0] = -nums[0]; for(int i =0; i < nums.size(); i++) sum += nums[i]; return sum; } };
二刷
class Solution { public: int largestSumAfterKNegations(vector<int>& nums, int k) { sort(nums.begin(),nums.end()); for(int i=0 ; i<nums.size() ;i++) { if(nums[i] <= 0 && k>0) { nums[i] = -nums[i]; k--; } } sort(nums.begin(),nums.end()); if(k%2 == 1) nums[0] = -nums[0]; int result = 0; for(int i=0 ; i<nums.size() ;i++) { result += nums[i]; } return result; } };
