Given an integer array nums and an integer k, modify the array in the following way:
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.
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 <= 104The key idea in #1005 Maximize Sum Of Array After K Negations is to use a greedy strategy that increases the array's total sum after exactly k sign changes. Since turning a negative value into a positive gives the largest gain, the goal is to prioritize negating the most negative elements first.
A common approach is to sort the array so that negative numbers appear first. Iterate through the array and flip negative values while you still have remaining operations. If all negatives are processed and operations remain, the final result depends on whether k is even or odd. If it is odd, flipping the element with the smallest absolute value minimizes the reduction in total sum.
This approach combines sorting and greedy decision-making to efficiently maximize the sum. Sorting helps identify which elements should be negated first, while tracking remaining operations ensures the optimal final configuration. The primary cost comes from sorting the array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Greedy | O(n log n) | O(1) or O(n) depending on sorting implementation |
| Min Heap Greedy | O(n log n + k log n) | O(n) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting places negative numbers at the beginning, making it easy to flip them first. This greedy step ensures each negation produces the maximum possible increase in the overall sum.
Yes, this type of greedy array optimization problem can appear in coding interviews at large tech companies. It tests understanding of greedy strategies, sorting, and edge-case handling.
An array with sorting is usually sufficient and efficient for this problem. Alternatively, a min-heap can be used to repeatedly flip the smallest element when performing k operations.
The optimal approach uses a greedy strategy. By sorting the array and flipping the most negative numbers first, you maximize the increase in total sum. If operations remain, you handle the smallest absolute value element depending on whether k is odd or even.