Watch 10 video solutions for Maximize Sum Of Array After K Negations, a easy level problem involving Array, Greedy, Sorting. This walkthrough by Fisher Coder has 2,945 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 104Problem Overview: You are given an integer array and allowed to negate (multiply by -1) exactly k elements. The same index can be chosen multiple times. The goal is to maximize the final sum of the array after performing these operations.
Approach 1: Sorting and Greedy Negation (O(n log n) time, O(1) extra space)
This approach relies on a greedy observation: negating negative numbers increases the total sum. Start by sorting the array so the most negative values appear first. Iterate from left to right and flip each negative number while k > 0. Each negation turns a loss into a gain. If you still have remaining operations after all negatives are handled, the optimal move depends on whether k is odd. When k is odd, negate the element with the smallest absolute value to minimize the damage. Sorting guarantees that the smallest values are processed first, making the greedy decision straightforward. This solution is simple and deterministic, which makes it the most common interview answer when discussing greedy techniques combined with sorting.
Approach 2: Using Priority Queue (Min-Heap) (O(k log n) time, O(n) space)
A min-heap provides a dynamic way to always access the smallest element in the array. Insert all numbers into a min-heap. For each of the k operations, extract the smallest value, negate it, and push it back into the heap. This guarantees that the currently most harmful value is flipped each time. The heap automatically reorders elements after each insertion, so you always operate on the optimal candidate. After performing k negations, sum all elements in the heap to compute the result. This method is useful when you want the algorithm to adapt after every operation rather than relying on a single sorted order. It highlights how priority queues can repeatedly expose the best greedy choice.
Recommended for interviews: The sorting-based greedy solution is typically expected. It shows that you understand the core insight: flipping negative numbers increases the sum, and a leftover odd operation should affect the smallest absolute value. Mentioning the heap approach demonstrates deeper understanding of greedy selection structures, but the sorted greedy implementation is simpler and runs in O(n log n) time with minimal overhead.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Greedy Negation | O(n log n) | O(1) | Best general solution. Simple greedy logic after sorting the array. |
| Priority Queue (Min-Heap) | O(k log n) | O(n) | Useful when repeatedly selecting the smallest element after each operation. |