We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Sum Of Array After K Negations

Number: 1047

Difficulty: Easy

Paid? No

Companies: Druva

Problem Description

Given an integer array nums and an integer k, you need to perform exactly k operations where you choose an index i and flip the sign of nums[i] (i.e., replace it with -nums[i]). The goal is to obtain the maximum possible sum of the array after exactly k modifications.

Key Insights

  • Sort the array to process the smallest (most negative) numbers first.
  • Flip negative numbers to positive, as they contribute more positively to the sum.
  • If flips remain after handling negatives, the optimal strategy involves flipping the smallest absolute value number, since flipping it impacts the sum minimally.
  • If additional flips are even, the overall sum remains unaffected; if odd, a final flip is needed on the smallest element.

Space and Time Complexity

Time Complexity: O(n log n), due to sorting the array. Space Complexity: O(1) extra space, assuming sorting is done in-place.

Solution

The solution begins by sorting the array in non-decreasing order. This ensures that all negative numbers come first. We then iterate through the sorted array, flipping negative numbers to positive until either we have no more negative numbers or we exhaust k flips. If flips remain after this process, we determine the smallest absolute value in the array. If the leftover k is odd, we subtract twice this minimum value from the cumulative sum to account for one extra flip that changes its sign. This greedy approach guarantees that the maximum sum is achieved.

Code Solutions

# Python code solution
def largestSumAfterKNegations(nums, k):
    # Sort the array to prioritize negatives
    nums.sort()
    
    # Flip negative numbers to positive
    for i in range(len(nums)):
        if k > 0 and nums[i] < 0:
            nums[i] = -nums[i]
            k -= 1
    
    # Sum of the array so far
    total_sum = sum(nums)
    
    # If k is odd, subtract twice the smallest element (flip minimum element once more)
    if k % 2 == 1:
        total_sum -= 2 * min(nums)
    
    return total_sum

# Example usage:
print(largestSumAfterKNegations([4,2,3], 1))
← Back to All Questions