algoadvance

Leetcode 1005. Maximize Sum Of Array After K Negations

Problem Statement

Given an integer array nums and an integer k, you need to maximize the sum of the array by modifying the array in the following way: You can repeat the operation of choosing an element from the array and negating it at most k times. Your goal is to maximize the sum of the array after performing exactly k negations.

Example 1:

Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose to negate the number 3, and the array becomes [4,2,-3].

Example 2:

Input: nums = [3,-1,0,2], k = 3
Output: 6
Explanation: Choose to negate -1 and then negate 0 two times. The array becomes [3,1,0,2].

Example 3:

Input: nums = [2,-3,-1,5,-4], k = 2
Output: 13
Explanation: Choose to negate -3 and -4, the array becomes [2,3,1,5,4].

Clarifying Questions

  1. Q: Can nums contain duplicate elements?
    A: Yes, nums can contain duplicate elements.

  2. Q: Is there a constraint on the size of nums?
    A: Yes, the length of nums can be up to 10,000.

  3. Q: Can the values in nums be zero or negative?
    A: Yes, the elements in nums can be zero, negative, or positive.

  4. Q: What are the limits of k?
    A: The value of k can be up to 10,000.

Strategy

  1. Sort the array nums.
  2. Prioritize negating the smallest numbers (which are negative) as they will have the most significant impact on the sum.
  3. After using up k negations or becoming unable to increase the sum further (if we run out of negative numbers to negate), we should decide based on parity of remaining k:
    • If k is even after the above steps, continue as remaining negations will cancel out.
    • If k is odd, negate the smallest absolute value in nums (because it minimizes the negative impact on the sum).

Code

Here’s the C++ implementation:

#include <vector>
#include <algorithm>
#include <numeric>

int largestSumAfterKNegations(std::vector<int>& nums, int k) {
    std::sort(nums.begin(), nums.end());
    
    for (int i = 0; i < nums.size() && k > 0; ++i) {
        if (nums[i] < 0) {
            nums[i] = -nums[i];
            --k;
        }
    }
    
    if (k % 2 == 1) {
        // If k is odd, flip the smallest element
        auto it = std::min_element(nums.begin(), nums.end());
        *it = -*it;
    }
    
    return std::accumulate(nums.begin(), nums.end(), 0);
}

Time Complexity

Overall, the time complexity is O(n log n) due to the sorting step.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI