LeetCode 1005: Maximize Sum Of Array After K Negations

Problem Restatement

We are given an integer array nums and an integer k.

In one operation, we choose an index and negate the value at that index.

We must perform exactly k operations.

We need to return the maximum possible sum of the array after exactly k negations.

The official constraints state that 1 <= nums.length <= 10^4, -100 <= nums[i] <= 100, and 1 <= k <= 10^4.

Input and Output

Function shape:

def largestSumAfterKNegations(nums: list[int], k: int) -> int:
    ...

Examples

Example 1:

nums = [4, 2, 3]
k = 1

Negate 2:

[4, -2, 3] -> sum = 5

Or negate 3:

[4, 2, -3] -> sum = 3

All numbers are positive and we must use exactly one negation. To lose as little sum as possible, negate the number with the smallest absolute value: 2.

That gives:

[4, -2, 3]

The sum is 5, which is the maximum possible after exactly one negation.

Answer:

5

Example 2:

nums = [3, -1, 0, 2]
k = 3

Negate -1 → [3, 1, 0, 2], then we have 2 more negations. Use remaining on 0 twice. Sum = 3 + 1 + 0 + 2 = 6.

Answer:

6

Example 3:

nums = [2, -3, -1, 5, -4]
k = 2

Negate -3 and -4: [2, 3, -1, 5, 4]. Sum = 2 + 3 + (-1) + 5 + 4 = 13.

Answer:

13

Key Insight

Greedy approach:

1. Negate the most negative numbers first (they become positive, increasing the sum the most).
2. If k negations remain after all negatives are turned positive, and k is odd, negate the smallest absolute value element once (to minimize the loss).

Algorithm

1. Sort nums numerically so negative numbers appear first.
2. For each element from smallest to largest: if negative and k > 0, negate it and decrement k.
3. After all negatives are handled, if k is odd, negate the element with the smallest absolute value.
4. Return the sum.

More precisely:

1. Sort nums.
2. Negate elements from smallest (most negative) while they are negative and k > 0.
3. If k is still odd, negate the element with minimum absolute value.
4. Return sum.

Correctness

Negating the most negative elements first always increases the sum by the maximum amount per operation.

Once all negatives are handled, any remaining operations on positive numbers will decrease the sum. To minimize this loss, negate the element with the smallest absolute value. If an even number of operations remain, we can negate the same element twice (net zero effect).

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def largestSumAfterKNegations(self, nums: list[int], k: int) -> int:
        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)

Code Explanation

Sort and negate negatives from smallest to largest:

nums.sort()
for i in range(len(nums)):
    if nums[i] < 0 and k > 0:
        nums[i] = -nums[i]
        k -= 1

If k is still odd, find the element with smallest absolute value and negate it:

if k % 2 == 1:
    nums.sort()
    nums[0] = -nums[0]

We re-sort because after negating negatives, the smallest element (by value) is now at the beginning.

Return the sum:

return sum(nums)

Testing

def run_tests():
    s = Solution()

    assert s.largestSumAfterKNegations([4, 2, 3], 1) == 5
    assert s.largestSumAfterKNegations([3, -1, 0, 2], 3) == 6
    assert s.largestSumAfterKNegations([2, -3, -1, 5, -4], 2) == 13
    assert s.largestSumAfterKNegations([-2, -3], 2) == 5
    assert s.largestSumAfterKNegations([1], 1) == -1

    print("all tests passed")

run_tests()