LeetCode 1005 - Maximize Sum Of Array After K Negations

The problem is asking us to maximize the sum of an integer array after performing exactly k negations. A negation operation consists of picking an index i and replacing nums[i] with -nums[i]. This operation can be applied to the same element multiple times.

leetcodeeasyarraygreedysorting

LeetCode Problem 1005

Difficulty: 🟢 Easy
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem is asking us to maximize the sum of an integer array after performing exactly k negations. A negation operation consists of picking an index i and replacing nums[i] with -nums[i]. This operation can be applied to the same element multiple times. The input consists of an array of integers nums and an integer k representing the number of negations. The expected output is the largest sum of the array that can be obtained after k such operations.

The constraints tell us that nums can be fairly large, up to 10,000 elements, and each element is within [-100, 100]. The number of operations k can also go up to 10,000. These constraints suggest that a brute-force approach that tries all combinations of negations will not be efficient enough.

Important edge cases include arrays with all positive numbers, all negative numbers, zeros, or when k is larger than the number of negative elements. The problem guarantees non-empty arrays and at least one operation, so we do not need to handle empty arrays or zero operations.

Approaches

The brute-force approach would try every possible sequence of k negations and compute the sum of the resulting array. While this approach guarantees correctness, its time complexity grows exponentially with k, making it infeasible for large arrays or large values of k. Specifically, it would require exploring n^k possibilities, which is far too slow for n and k up to 10,000.

The optimal approach leverages two key observations. First, to maximize the sum, we should prioritize negating the smallest (most negative) numbers first, because turning a large negative number into a positive number increases the sum the most. Second, after all negative numbers are flipped, if k is still greater than zero, repeated negations on the smallest absolute value element will minimize the reduction in sum, since flipping the smallest element introduces the smallest negative impact.

The optimal solution involves sorting the array to efficiently access the smallest elements, flipping negative numbers first, and handling any remaining k by flipping the smallest absolute value as needed.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^k) O(n) Tries all sequences of negations, exponential time
Optimal O(n log n) O(1) Sorts array, flips negatives, handles remaining k with smallest absolute value

Algorithm Walkthrough

  1. Sort the array nums in ascending order. This ensures negative numbers come first and the smallest absolute values are easy to find.
  2. Iterate over the array. For each negative number, flip it (multiply by -1) and decrement k by 1. Continue until either all negative numbers are flipped or k reaches zero.
  3. If k is still greater than zero after the first pass, find the element with the smallest absolute value in the array. If k is odd, flip this element once. If k is even, no further action is needed because flipping twice cancels out.
  4. Return the sum of the modified array.

Why it works: The algorithm maintains the invariant that at each step, the array is being modified in the way that maximally increases the sum. Flipping negative numbers first ensures the largest possible gains, and handling the remaining k with the smallest absolute value ensures minimal loss if an odd flip remains.

Python Solution

from typing import List

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        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:
            nums.sort()
            nums[0] = -nums[0]
        return sum(nums)

This Python implementation first sorts the array to prioritize negative numbers. It then flips as many negative numbers as allowed by k. If k is still odd, it flips the smallest absolute value number to minimize the reduction in sum. Finally, it returns the sum of the modified array.

Go Solution

import "sort"

func largestSumAfterKNegations(nums []int, k int) int {
    sort.Ints(nums)
    for i := 0; i < len(nums) && k > 0; i++ {
        if nums[i] < 0 {
            nums[i] = -nums[i]
            k--
        }
    }
    if k%2 == 1 {
        sort.Ints(nums)
        nums[0] = -nums[0]
    }
    sum := 0
    for _, v := range nums {
        sum += v
    }
    return sum
}

The Go version mirrors the Python logic. Sorting and flipping operations are done in-place. The difference is the explicit sum calculation with a for-range loop, since Go does not have a built-in sum function for slices.

Worked Examples

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

After sorting: [2,3,4]. No negative numbers, k is odd, flip smallest element 2 → [-2,3,4]. Sum = 5.

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

After sorting: [-1,0,2,3]. Flip -1 → [1,0,2,3], k = 2. No more negatives. Smallest absolute = 0, flipping does nothing. k still 2 → even, sum = 6.

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

After sorting: [-4,-3,-1,2,5]. Flip -4 → [4,-3,-1,2,5], k = 1. Flip -3 → [4,3,-1,2,5], k = 0. Sum = 13.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, iterating once over array is O(n)
Space O(1) In-place sorting and modifications, no extra structures

Sorting is the key operation. All other steps are linear scans, so overall complexity is dominated by O(n log n).

Test Cases

# Provided examples
assert Solution().largestSumAfterKNegations([4,2,3], 1) == 5  # Example 1
assert Solution().largestSumAfterKNegations([3,-1,0,2], 3) == 6  # Example 2
assert Solution().largestSumAfterKNegations([2,-3,-1,5,-4], 2) == 13  # Example 3

# Edge and boundary cases
assert Solution().largestSumAfterKNegations([-2,-3,-1], 3) == 6  # all negatives, k odd
assert Solution().largestSumAfterKNegations([1,2,3], 2) == 6  # all positives, k even
assert Solution().largestSumAfterKNegations([0,0,0], 1) == 0  # zeros only
assert Solution().largestSumAfterKNegations([1], 1) == -1  # single element
assert Solution().largestSumAfterKNegations([-5, -2, 1], 10) == 8  # k >> negatives
Test Why
[4,2,3], k=1 Basic positive numbers, single negation
[3,-1,0,2], k=3 Mix of negatives, zero, multiple negations
[2,-3,-1,5,-4], k=2 Multiple negatives, multiple flips
[-2,-3,-1], k=3 All negatives, odd k
[1,2,3], k=2 All positives, even k should not change sum
[0,0,0], k=1 Zeros edge case, flipping does not change sum
[1], k=1 Single element, ensures array indexing works
[-5,-2,1], k=10 Large k compared to negative numbers

Edge Cases

One important edge case is when all numbers are positive and k is odd. Flipping any number reduces the sum, so the algorithm must choose the smallest number to minimize loss.

Another edge case is when the array contains zeros. Flipping zero does not change the sum, which can be useful if k is odd, as it allows satisfying the operation count without reducing the sum.

A third edge case is when k is larger than the number of negative numbers. After flipping all negatives, the algorithm needs to correctly handle remaining flips. If k is even, no further action is needed; if odd, it flips the smallest absolute value element to minimize impact. This is correctly handled by the final conditional check in both Python and Go implementations.