You are given a list of integers nums and an integer k. You must perform exactly k sign flips: each flip picks one element and multiplies it by -1. The same element may be flipped more than once. Return the largest possible sum of the list after the k flips.
Examples
Input: nums = [4, 2, 3], k = 1
Output: 5
Explanation: every element is positive, so the best you can do is flip the smallest: 4 - 2 + 3.
Input: nums = [3, -1, 0, 2], k = 3
Output: 6
Explanation: flip -1 to 1, then spend the remaining two flips on the 0. Sum 3 + 1 + 0 + 2.
Input: nums = [2, -3, -1, 5, -4], k = 2
Output: 13
Explanation: flip -4 and -3: 2 + 3 - 1 + 5 + 4.
Constraints
1 <= len(nums) <= 10**5,-10**4 <= nums[i] <= 10**41 <= k <= 10**5- Target complexity: O(n + k log n).
Goals
- Recognise that the best value to negate is always the current minimum
- Apply exactly k operations even when they stop being useful
- Use heapreplace to pop and push in one step