Maximize Sum Of Array After K Negations

The key idea

Sort ascending and flip the most-negative numbers first, since flipping a value v changes the sum by -2v — biggest gain comes from the smallest (most negative) v. After the negatives are gone, any leftover flips come in pairs that cancel; only a single odd leftover flip matters, and it should hit the smallest absolute value to cost the least.

Problem

You are given an integer array nums and an integer k. You may choose any index i and replace nums[i] with -nums[i]. You must apply this operation exactly k times (you may pick the same index more than once).

After performing the operations, return the maximum possible sum of the array.

Constraints

1 <= nums.length <= 10^4
-100 <= nums[i] <= 100
1 <= k <= 10^4

Examples

Input: nums = [4,2,3], k = 1 Output: 5

Input: nums = [3,-1,0,2], k = 3 Output: 6

Input: nums = [2,-3,-1,5,-4], k = 2 Output: 13

Complexity

Time: O(n log n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →