LeetCode 1005. K 次取反后最大化的数组和
给你一个整数数组 nums
和一个整数 k
,按以下方法修改该数组:
选择某个下标 i
并将 nums[i]
替换为 -nums[i]
。
重复这个过程恰好 k
次。可以多次选择同一个下标 i
。
以这种方式修改数组后,返回数组 可能的最大和 。
示例 1:
输入:nums = [4,2,3], k = 1
输出:5
解释:选择下标 1 ,nums 变为 [4,-2,3]
示例 2:
输入:nums = [3,-1,0,2], k = 3
输出:6
解释:选择下标 (1, 2, 2) ,nums 变为 [3,1,0,2]
method
把越大的负数取反收益最大,如果都是正数了,就把最小的那个数连续多次取反,把k
消耗掉,这样损失最小
static bool cmp(const int a, const 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 & 1) nums.back() *= -1;
int res = 0;
for (auto n : nums) res += n;
return res;
}