Maximize Sum Of Array After K Negations: Greedy Sorting Pattern

Given an integer array nums and an integer k, you must choose an element and negate it (flip its sign) exactly k times. You can negate the same element more than once. Return the largest possible sum of the array after performing all k negations.

This is LeetCode 1005: Maximize Sum Of Array After K Negations, an easy problem that teaches the greedy sorting pattern. The core idea is to always negate the smallest element in the array, because flipping a negative number to positive gives you the biggest improvement to your sum.

Why this problem matters

This problem is one of the clearest introductions to the greedy-with-sorting pattern. You sort to bring the most impactful elements to the front, then make a series of locally optimal choices that turn out to be globally optimal. The same approach applies to problems like assigning cookies, minimizing costs, and distributing resources.

It also teaches you to think about what happens when you run out of "useful" negations. Once all numbers are positive, the remaining negations need careful handling. That leftover-k logic is a common source of bugs, and practicing it here builds good habits.

The key insight

Negating a negative number always increases the sum. Negating a positive number always decreases it. So the greedy strategy is clear: negate the most negative numbers first to get the biggest gains. Once all numbers are positive (or you run out of k), you handle the remainder.

Here is the full algorithm:

1. Sort the array in ascending order so the most negative values come first.
2. Walk through the array. For each negative element, negate it (make it positive) and decrement k. Stop when k reaches 0 or there are no more negatives.
3. If k is still greater than 0 and k is odd, you need one more negation. Find the element with the smallest absolute value in the array and negate it. If k is even, the extra negations cancel out (negate and un-negate the same element).
4. Return the sum of the array.

The solution

def largestSumAfterKNegations(nums, k):
    nums.sort()
    for i in range(len(nums)):
        if nums[i] < 0 and k > 0:
            nums[i] = -nums[i]
            k -= 1
    if k % 2 == 1:
        nums.sort()
        nums[0] = -nums[0]
    return sum(nums)

The first sort() puts the most negative values at the front. The loop negates them one by one, spending k as it goes. After the loop, if k is still odd, we sort again and negate the smallest element. That second sort is needed because the element with the smallest absolute value might not be at index 0 after the first pass. Finally, we return the total sum.

Visual walkthrough

Notice that each negation of a negative number increases the sum by twice that number's absolute value. Negating -8 adds 16 to the sum. Negating -5 adds 10. This is why sorting matters: you want to capture the largest gains first.

Complexity analysis

Time: The dominant cost is sorting, which takes O(n log n). The single pass through the array is O(n), and the optional second sort is also O(n log n). Overall: O(n log n).

Space: The sort is done in-place, and we only use a few variables. O(1) extra space (or O(n) if your language's sort is not in-place).

The building blocks

1. Sort-then-greedy

Many greedy problems start by sorting the input to create a predictable order for decision-making. By placing the most negative numbers first, you guarantee that each negation gives the maximum possible improvement. This same pattern appears in Assign Cookies (sort both arrays, then greedily match) and Minimum Number of Arrows to Burst Balloons (sort intervals by endpoint).

2. Parity of remaining operations

After exhausting all useful negations, you need to handle leftover k. The key observation is that two negations on the same element cancel out. So only the parity of k matters: if k is even, do nothing; if k is odd, negate the smallest absolute value element once. This "parity trick" shows up in many problems where operations can be undone.

Edge cases

• All positive values: sorting puts the smallest positive first. If k is odd, you negate that smallest element. If k is even, the array stays unchanged.
• All negative values with k equal to the array length: every element gets negated to positive. No leftover k to worry about.
• k larger than the number of negatives: negate all negatives, then apply the parity check on the remaining k.
• Array with zeros: if there is a zero in the array, any leftover odd k can be "absorbed" by negating zero (which has no effect on the sum).
• Single element: negate it k times. If k is odd the element flips sign; if k is even it stays the same.

From understanding to recall

The greedy logic here is clean: sort, negate negatives, handle leftover k by parity. Three steps. But under interview pressure, the details trip people up. Do you sort again before handling leftover k? Do you check k % 2 == 1 or k > 0? Do you negate the smallest element or the last negated element?

Spaced repetition locks in these details. You write the solution from scratch at increasing intervals until the pattern is automatic. After a few rounds, you see "maximize sum with k negations" and the sorted-greedy approach flows out without hesitation.

The sort-then-greedy pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Assign Cookies - Another greedy sorting problem
• Smallest Range I - Greedy approach to minimize range
• Sort Colors - Array manipulation with sorting insight

CodeBricks breaks the maximize sum after k negations LeetCode problem into its sort-then-greedy and parity-of-operations building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy sorting question shows up in your interview, you do not think about it. You just write it.