Domain 1EasyCORE

Maximize Sum Of Array After K Negations

We are given an array `A` of integers and an integer `K`. The task is to modify the array by negating any element up to `K` times. After performing these negations, we need to return the maximum possible sum of the array.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Greedy

1005. Maximize Sum Of Array After K Negations

Model: qwen2.5-coder:14b
Topics: Greedy
FAANG asked: 1
Acceptance rate: 52.3%


Problem Breakdown

We are given an array A of integers and an integer K. The task is to modify the array by negating any element up to K times. After performing these negations, we need to return the maximum possible sum of the array.

Inputs:

  • An array A of integers.
  • An integer K representing the number of negations allowed.

Outputs:

  • The largest possible sum of the array after performing up to K negations.

Implicit Constraints and Edge Cases:

  • If K is 0, no changes should be made to the array.
  • If all elements are non-negative, negating any element will decrease the sum.
  • If there are negative numbers, negating them can increase the sum.
  • The array can contain zeros, which do not change when negated.
  • The size of the array and K can be up to 10,000, so the solution should be efficient in terms of time and space.

Intuition

A brute-force approach would involve trying all possible combinations of negations, but this is computationally expensive with a time complexity of O(2^K), which is not feasible given the constraints.

The key insight is to prioritize negating the smallest (most negative) numbers first. This way, we maximize the increase in the sum for each negation. If there are still negations left after processing all elements, and K is odd, we should negate the smallest absolute value element one last time to minimize the impact on the sum.

Approach

  1. Sort the Array: Start by sorting the array. This allows us to easily access the smallest (most negative) numbers.
  2. Negate Elements: Iterate through the sorted array and negate elements until we have used up all K negations or there are no more negative numbers left.
  3. Handle Remaining Negations: If there are still negations left (K is odd), negate the smallest absolute value element one last time.
  4. Calculate the Sum: Finally, calculate the sum of the modified array.

Complexity Analysis

  • Time Complexity: O(n log n) due to sorting the array, where n is the length of the array.
  • Space Complexity: O(1) if we sort the array in place and use a constant amount of extra space.

Solution

def largestSumAfterKNegations(A, K):
    # Sort the array to access the smallest elements first
    A.sort()
    
    # Negate the smallest elements up to K times
    for i in range(len(A)):
        if A[i] < 0 and K > 0:
            A[i] = -A[i]
            K -= 1
    
    # If there are still negations left and K is odd, negate the smallest element
    if K % 2 == 1:
        A.sort()
        A[0] = -A[0]
    
    # Calculate and return the sum of the modified array
    return sum(A)

Edge Cases Handled

  • All elements are non-negative: The array remains unchanged, and the sum is returned as is.
  • All elements are negative: Negating all elements will increase the sum.
  • Array contains zeros: Zeros do not change when negated, so they are ignored in the process.
  • K is 0: No changes are made to the array, and the original sum is returned.
  • K is greater than the number of negative elements: After negating all negative elements, if K is still odd, we negate the smallest element to minimize the impact on the sum.