Skip to main content

Maximize Sum of Array After K Negations

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.

Examples

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 <= 10^4
  • -100 <= nums[i] <= 100
  • 1 <= k <= 10^4

Solution for Largest Sum After K Negations Problem

To solve this problem, we should follow a greedy approach by repeatedly negating the smallest element in the array, as this will maximize the sum after k operations.

Approach

  1. Sort the Array:

    • Sort the array to bring all the negative numbers to the front.
  2. Negate the Minimum Element:

    • Iterate through the array and negate the smallest elements (negative numbers) first.
    • If there are still operations left after negating all negative numbers, use the remaining operations on the smallest absolute value element.
  3. Handle Remaining Operations:

    • If k is still greater than 0 after negating all negative numbers, continue to negate the smallest absolute value element until k becomes 0.

Code in Different Languages

Written by @ImmidiSivani
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
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) {
*min_element(nums.begin(), nums.end()) *= -1;
}
return accumulate(nums.begin(), nums.end(), 0);
}
};

Complexity Analysis

  • Time Complexity: O(nlogn)O(n \log n), where n is the length of the array. This is due to the sorting step.
  • Space Complexity: O(1)O(1), as we are modifying the array in place.

Authors:

Loading...