Maximize Sum Of Array After K Negations
Problem
You may negate k elements (with repetition allowed). Maximize the final sum.
nums = [4,2,3], k = 15def largestSumAfterKNegations(nums, k):
nums.sort()
for i in range(len(nums)):
if k > 0 and nums[i] < 0:
nums[i] = -nums[i]; k -= 1
if k % 2 == 1:
m = min(range(len(nums)), key=lambda i: nums[i])
nums[m] = -nums[m]
return sum(nums)function largestSumAfterKNegations(nums, k) {
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
if (k > 0 && nums[i] < 0) { nums[i] = -nums[i]; k--; }
}
if (k % 2 === 1) {
let mi = 0;
for (let i = 1; i < nums.length; i++) if (nums[i] < nums[mi]) mi = i;
nums[mi] = -nums[mi];
}
return nums.reduce((a, b) => a + b, 0);
}class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++)
if (k > 0 && nums[i] < 0) { nums[i] = -nums[i]; k--; }
if (k % 2 == 1) {
int mi = 0;
for (int i = 1; i < nums.length; i++) if (nums[i] < nums[mi]) mi = i;
nums[mi] = -nums[mi];
}
int sum = 0; for (int v : nums) sum += v; return sum;
}
}int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
for (int i = 0; i < (int)nums.size(); i++)
if (k > 0 && nums[i] < 0) { nums[i] = -nums[i]; k--; }
if (k % 2 == 1) {
int mi = 0;
for (int i = 1; i < (int)nums.size(); i++) if (nums[i] < nums[mi]) mi = i;
nums[mi] = -nums[mi];
}
return accumulate(nums.begin(), nums.end(), 0);
}Explanation
To make the sum as large as possible, we want to flip the most negative numbers into positives first, since each such flip adds the most. The strategy is greedy: sort, flip negatives left to right, then handle any leftover flips carefully.
After sorting ascending, we walk left to right and, while we still have flips (k > 0) and the value is negative, we negate it and spend one flip. This turns the biggest negatives positive.
If flips remain after that, only positives are left. Flipping a number twice cancels out, so what matters is whether k is odd. If it is, we waste one flip on the element with the smallest absolute value, losing the least.
Finally we add everything up. Choosing the smallest magnitude for the unavoidable extra flip keeps the damage minimal.
Example: nums = [4, 2, 3], k = 1. No negatives to flip, and k=1 is odd, so we flip the smallest value 2 to -2: sum becomes 4 + (-2) + 3 = 5.