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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximize Sum Of Array After K Negations

Difficulty: Easy

Problem Description

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.

Key Insights

  • The goal is to maximize the sum of the array after performing k negations.
  • Negating a positive number decreases the sum, while negating a negative number increases the sum.
  • The best strategy is to always negate the smallest absolute value in the array when k allows.
  • If there are remaining negations after all negative numbers are made positive, they can negate the smallest positive number.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array. Space Complexity: O(1) - no additional data structures are used apart from input storage.

Solution

To solve this problem, we can use a greedy approach. The algorithm involves the following steps:

  1. Sort the array based on the absolute values of its elements.
  2. Iterate through the sorted array and negate the smallest absolute value k times.
  3. If k is still greater than zero after negating all negative values, the remaining negations should be applied to the smallest positive number (or the smallest absolute value in the array).
  4. Finally, calculate and return the sum of the modified array.

Code Solutions

def largestSumAfterKNegations(nums, k):
    nums.sort(key=abs)  # Sort based on absolute values
    for i in range(len(nums)):
        if k > 0 and nums[i] < 0:
            nums[i] = -nums[i]  # Negate the negative numbers
            k -= 1
    # If there are still negations left
    if k % 2 == 1:
        nums.sort()  # Sort the array to find the smallest element
        nums[0] = -nums[0]  # Negate the smallest element
    return sum(nums)  # Return the sum of the modified array
← Back to All Questions