给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。
> 我的解法
class Solution {
public:
//取反的顺序为 负数、0、正数（优先级是小的优先）
int largestSumAfterKNegations(vector<int>& nums, int k) {
std::sort(nums.begin(),nums.end());
int len = nums.size();
int target = 0;
if(*nums.begin() > 0){
k = k%2;
if(k == 1){
nums[0] = -nums[0];
}
}
else if(*nums.begin() < 0){
auto iter = std::find(nums.begin(),nums.end(),0);
if(iter == nums.end()){
for(int i = 0;i < len && k > 0 && nums[i] < 0;i++){
nums[i] = - nums[i];
k--;
}
if(k > 0){
return largestSumAfterKNegations(nums,k);
}
}
else{
for(auto it = nums.begin();it != iter && k > 0; it++){
*it = -*it;
k--;
}
}
}
int sum = 0;
for(const auto &a:nums){
sum += a;
}
return sum;
}
};
> 贪心解法
class Solution {
static bool cmp(int a, int b) {
return abs(a) > abs(b);
}
public:
int largestSumAfterKNegations(vector<int>& A, int K) {
sort(A.begin(), A.end(), cmp); // 第一步
for (int i = 0; i < A.size(); i++) { // 第二步
if (A[i] < 0 && K > 0) {
A[i] *= -1;
K--;
}
}
if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
int result = 0;
for (int a : A) result += a; // 第四步
return result;
}
};