Maximize Sum After K Negations

Maximize Sum After K Negations is a clean greedy problem. You are handed exactly k flips to spend, and the trick is realizing that a sorted array tells you precisely where each flip does the most good.

The slow way first

You could try every assignment of the k flips across the elements and keep the best sum. That explodes combinatorially and is hopeless for large k.

The question to ask: which flip helps the most right now? Turning a negative number positive is a pure gain — and the more negative it is, the bigger that gain. So the flips should always go to the most-negative numbers first.

The idea: greedily flip the most-negative

Sort ascending so the most-negative values sit on the left. Walk left to right, flipping each negative to positive while k > 0. Once you reach a non-negative number, stop — flipping a positive only loses value.

If flips remain after that, they come in pairs that cancel (flipping the same number twice is a no-op), so only the parity of the leftover k matters. If k is odd, you are forced into exactly one extra flip, so spend it on the number with the smallest absolute value to lose as little as possible.

The key insight: greedy works here because each flip is independent, and the best flip is always the most-negative remaining element.

Walk through it

Step through the animation. After sorting we see -4, -2, 1, 3. The pointer i flips -4 and -2 to positive, dropping k from 5 to 3. At 1 the loop stops. k = 3 is odd, so one flip remains — we spend it on the smallest magnitude, turning 1 into -1. The final sum is 8.

Pseudocode

sort nums ascending
for each index i:
    if k > 0 and nums[i] < 0:
        nums[i] = -nums[i]            # flip a negative to positive
        k -= 1
if k is odd:                          # leftover pairs cancel out
    flip the element with smallest absolute value
return sum(nums)

The Python solution

def largest_sum_after_negations(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:
        smallest = min(nums)
        idx = nums.index(smallest)
        nums[idx] = -nums[idx]
    return sum(nums)

• nums.sort() puts the most-negative numbers on the left, where flips pay off most.
• The loop flips each negative to positive while flips remain; it naturally stops paying out once values turn non-negative.
• k % 2 == 1 checks the leftover parity — an even leftover cancels itself, so only an odd remainder forces action.
• When forced, min(nums) finds the smallest value after the flips (every flipped element is now positive), which is the smallest magnitude to sacrifice.
• sum(nums) returns the maximized total.

Complexity

The sort dominates at O(n log n); everything after is a linear sweep. We modify the array in place, so no extra space beyond the sort.

When this pattern shows up

Practice