You are given a list nums and an integer k. You must perform exactly k sign flips, where one flip picks any index i and replaces nums[i] with -nums[i]. The same index may be flipped more than once. Return the largest sum the list can have after all k flips.
Examples
Input: nums = [4, -2, 3, -1], k = 2
Output: 10
Explanation: Flip -2 and -1 to get [4, 2, 3, 1].
Input: nums = [2, 3, 5], k = 1
Output: 6
Explanation: The single flip must hit something; flipping 2 costs the least.
Constraints
1 <= len(nums) <= 10**5,-10**4 <= nums[i] <= 10**4,1 <= k <= 10**9.- Target complexity: O(n log n).
Goals
- Spend flips on the most negative values first
- Handle leftover flips with a parity argument