142. Maximize Array Sum After K Negations

Given an array of n integers and a number k, you may repeatedly choose any element and flip its sign, doing this exactly k times in total (the same element can be chosen more than once). Find the maximum possible sum of the array afterward.

Input: The first line contains an integer n. The second line contains n space-separated integers, the array elements. The final line contains k, the number of sign flips to perform. Output: Print a single integer - the maximum possible sum of the array after exactly k flips.

1 <= n <= 10^5, 0 <= k <= 10^5

If k is EVEN after flipping all negatives, and the smallest remaining value happens to be 0, further flips do nothing (flipping 0 stays 0) - a subtle edge case worth being aware of, though it doesn't change the greedy strategy's correctness.

Flip the sign of any array elements (reusable) exactly k times total, to maximize the resulting sum. Brute force: Try every possible combination of which elements to flip (and how many times each) - this is exponential, when a simple greedy 'always flip the current minimum' rule is provably optimal. Optimised: Flipping the CURRENT smallest element always gives the biggest possible improvement to the sum at each step (turning the most negative value into the most positive gain) - a min-heap lets you repeatedly find and update this smallest element in O(log n) per flip, rather than re-scanning the whole array each time.

Build a min-heap from all n elements in O(n). Repeat exactly k times: pop the current minimum element, negate it, and push it back into the heap; this always flips the currently most negative (or smallest) value, which is provably the best single flip to maximize the sum at each step, and naturally handles a value being flipped back and forth if that becomes optimal. After k pops/pushes, sum all elements in the heap (or maintain a running total updated by twice the negated value's magnitude at each step) to get the final answer. This handles the repeated-flip nature of the problem directly via the heap's ordering. Time: O(n + k log n) Space: O(n)

Sort the array ascending in O(n log n). Scan from the start, and while k > 0 and the current element is negative, flip its sign (turning it positive, which always increases the sum) and move to the next element, decrementing k each time. If k reaches 0 partway through, stop; if all negatives get flipped and k remains, and k is odd, flip the sign of whichever remaining element has the smallest absolute value once more (since flipping any element an even number of additional times changes nothing, only a single leftover flip matters, and it should hit the smallest magnitude element to minimize the loss). Sum the resulting array. Time: O(n log n) Space: O(1) extra

Recursively try, at each of the k steps, flipping the sign of every possible index in the array and branching into the resulting array state, continuing until k flips have been made, and take the maximum final sum found across all explored sequences. Because the same index can be flipped multiple times (which can cancel out) and every step branches over all n indices, this explores an enormous space of possible flip sequences. Time: O(n^k) Space: O(k) recursion depth

1. Always flip the CURRENT smallest (most negative) element - this is the greedy choice at every single step. 2. A min-heap makes repeatedly finding and updating the current smallest element efficient. 3. Repeat this exactly k times, then sum the final array.

Time: O((n + k) log n) - building the heap costs O(n), and each of the k flips costs O(log n). Space: O(n), for the heap.

k = 0 (array unchanged), k greater than the count of negative numbers (leftover flips reuse the same smallest element repeatedly), and n at its maximum of 10^5 with k up to 10^5 to confirm the heap-based approach runs efficiently.

Be ready to mention the sorting-based alternative (sort ascending, flip all negatives while k allows, then handle any leftover k by repeatedly flipping the current minimum) as an equally valid, sometimes simpler-to-reason-about approach.