class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int sum=0;
for(int i=0;i<nums.size();i++){
sum+=nums[i];
}
while(k--){
int min=0;
for(int i=0;i<nums.size();i++){
if(nums[min]>nums[i]) min=i;
}
nums[min]=-nums[min];
sum+=nums[min]*2;
}
return sum;
}
};
取反k次,贪心贪的是每次都取反最小的那个数,因为最小负数取反后收益最大,最小正数取反后损失最小,具体实现就是先求出总和,然后再while循环里面对最小值重新令为其绝对值,循环次数为k,sum再加上两倍最小值的绝对值,循环结束返回sum
?
class Solution {
public:
static bool cmp(int a,int b){
return abs(a)>abs(b);
}
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(),nums.end(),cmp);
for(int i=0;i<nums.size();i++){
if(nums[i]<0&&k>0){
nums[i]*=-1;
k--;
}
}
if(k%2){
nums[nums.size()-1]*=-1;
}
int sum=0;
for(int a:nums){
sum+=a;
}
return sum;
}
};
?下面这种解法时间复杂度更低,首先对数组的绝对值从大到小排序,然后遍历数组,如果nums[i]为负同时k不为0,则从左到右依次对负数取绝对值,如果k为0了则累加数组就行,如果nums[i]为正了,则先判断k的奇偶,如果为偶数直接累加,如果为奇数则对数组末数值去绝对值,然后累加