{x}
blog image

Maximize Sum Of Array After K Negations

Given an integer array nums and an integer k, modify the array in the following way:

  • choose an index i and replace nums[i] with -nums[i].

You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

 

Example 1:

Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose index 1 and nums becomes [4,-2,3].

Example 2:

Input: nums = [3,-1,0,2], k = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

Example 3:

Input: nums = [2,-3,-1,5,-4], k = 2
Output: 13
Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].

 

Constraints:

  • 1 <= nums.length <= 104
  • -100 <= nums[i] <= 100
  • 1 <= k <= 104

Solution Explanation for Maximize Sum Of Array After K Negations

This problem asks to maximize the sum of an array after negating at most K elements. The optimal strategy is a greedy approach:

  1. Sort the Array: Sort the array in ascending order. This ensures that we first negate the smallest elements, which will likely lead to the largest possible sum increase.

  2. Negate Negative Numbers: Iterate through the sorted array. As long as you have k negations remaining and encounter a negative number, negate it.

  3. Handle Even K and Zero: If k is even after negating all the negative numbers, you've reached the optimal sum. If k is odd, you may choose to negate the smallest positive number (or zero, as it doesn't change the sum) to further maximize.

Time Complexity: O(N log N), dominated by the sorting step. The subsequent iteration through the array takes O(N) time.

Space Complexity: O(1) if sorting is done in place; otherwise, O(N) if a new sorted array is created.

Code Implementations

The following code implements this greedy strategy in several languages:

Python

def largestSumAfterKNegations(nums, k):
    nums.sort()  # Sort in ascending order
    n = len(nums)
    i = 0
    while i < n and k > 0 and nums[i] < 0:
        nums[i] *= -1  # Negate negative numbers
        k -= 1
        i += 1
    
    if k > 0:  # Handle odd k
        nums.sort()  #Sort again to find the smallest element
        nums[0] *= (1 if k % 2 == 1 else 1) #negate the smallest element if k is odd
 
    return sum(nums)

Java

import java.util.Arrays;
 
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums); // Sort in ascending order
        int n = nums.length;
        int i = 0;
        while (i < n && k > 0 && nums[i] < 0) {
            nums[i] *= -1; // Negate negative numbers
            k--;
            i++;
        }
        if (k > 0) { //Handle odd k
            Arrays.sort(nums); // Sort again to find the smallest
            nums[0] *= (k % 2 == 1 ? -1 : 1); //negate the smallest element if k is odd
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }
}

C++

#include <algorithm>
#include <numeric> // for accumulate
 
int largestSumAfterKNegations(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end()); // Sort in ascending order
    int n = nums.size();
    int i = 0;
    while (i < n && k > 0 && nums[i] < 0) {
        nums[i] *= -1; // Negate negative numbers
        k--;
        i++;
    }
    if (k > 0) { //Handle odd k
        sort(nums.begin(), nums.end()); //Sort again to find the smallest
        nums[0] *= (k % 2 == 1 ? -1 : 1); //negate the smallest element if k is odd
 
    }
    return accumulate(nums.begin(), nums.end(), 0); //Efficiently calculate sum
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestSumAfterKNegations = function(nums, k) {
    nums.sort((a, b) => a - b); // Sort in ascending order
    let i = 0;
    while (i < nums.length && k > 0 && nums[i] < 0) {
        nums[i] *= -1; // Negate negative numbers
        k--;
        i++;
    }
    if (k > 0) {  //Handle odd k
        nums.sort((a, b) => a - b); //Sort again to find the smallest
        nums[0] *= (k % 2 === 1 ? -1 : 1); //negate the smallest element if k is odd
 
    }
    return nums.reduce((sum, num) => sum + num, 0);
};

These examples all follow the same core logic: sort, negate negatives, and handle the final odd k case. Remember to choose the implementation that best suits your preferred language and coding style.