Maximize Sum Of Array After K Negations
EasyPrompt
Given an integer array nums and an integer k, modify the array in the following way:
- choose an index
iand replacenums[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] <= 1001 <= k <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the given process. It iterates k times, and in each iteration, it finds the smallest element in the array and negates it. This is the most straightforward way to implement the logic but is not the most efficient.
Algorithm
- Initialize a loop to run
ktimes. - Inside the loop, find the index
minIndexof the smallest element in the arraynumsby iterating through it. - Negate the element at this index:
nums[minIndex] = -nums[minIndex]. - After the loop completes, iterate through the modified
numsarray one last time to calculate the total sum. - Return the calculated sum.
Walkthrough
The core idea is to repeatedly perform the operation that seems best at the current moment: negating the smallest number to get the largest possible immediate increase in sum. We loop exactly k times. In each iteration, we perform a linear scan of the entire array to find the minimum value and its index. Once found, we flip its sign. After k iterations, the array is in its final state, and we compute the sum of all its elements.
class Solution { public int largestSumAfterKNegations(int[] nums, int k) { for (int i = 0; i < k; i++) { int minIndex = 0; for (int j = 1; j < nums.length; j++) { if (nums[j] < nums[minIndex]) { minIndex = j; } } nums[minIndex] = -nums[minIndex]; } int sum = 0; for (int num : nums) { sum += num; } return sum; }}Complexity
Time
O(k * N). To find the minimum element, we must scan the entire array of size N. This operation is repeated `k` times, leading to a total time complexity of O(k * N).
Space
O(1). The array is modified in-place, so no extra space proportional to the input size is used.
Trade-offs
Pros
Simple to understand and implement.
Follows the problem description literally.
Uses constant extra space.
Cons
Highly inefficient for large values of
kandN, as it repeatedly scans the entire array.Likely to result in a "Time Limit Exceeded" error on platforms with strict time limits for the given constraints.
Solutions
Solution
class Solution {public int largestSumAfterKNegations(int[] nums, int k) { Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) { cnt.merge(x, 1, Integer : : sum); } for (int x = -100; x < 0 && k > 0; ++x) { if (cnt.getOrDefault(x, 0) > 0) { int m = Math.min(cnt.get(x), k); cnt.merge(x, -m, Integer : : sum); cnt.merge(-x, m, Integer : : sum); k -= m; } } if ((k & 1) == 1 && cnt.getOrDefault(0, 0) == 0) { for (int x = 1; x <= 100; ++x) { if (cnt.getOrDefault(x, 0) > 0) { cnt.merge(x, -1, Integer : : sum); cnt.merge(-x, 1, Integer : : sum); break; } } } int ans = 0; for (var e : cnt.entrySet()) { ans += e.getKey() * e.getValue(); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.