Given an integer array nums and an integer k, modify the array in the following way:


	choose an index 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.

&nbsp;
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].


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 104
	-100 &lt;= nums[i] &lt;= 100
	1 &lt;= k &lt;= 104


from heapq import heapify, heapreplace

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        heapify(nums)
        while k and nums[0] < 0:
            heapreplace(nums, -nums[0])
            k -= 1
        if k % 2:
            heapreplace(nums, -nums[0])
        return sum(nums)
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int val : nums) minHeap.add(val);

        while(k > 0){

            int curr = minHeap.poll();
            minHeap.add(-curr);
            k--;
        }

        int sum = 0;
        while(!minHeap.isEmpty()){
            sum += minHeap.poll();
        }
        return sum;
    }
}
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int k) {
       priority_queue<int, vector<int>, greater<int>> pq(A.begin(), A.end());
        while(k--){
            int t=pq.top();pq.pop();
            pq.push(t*-1);
        }
    
        int n=0;
       while(!pq.empty()){
           int t=pq.top();pq.pop();
           n+=t;
       }
        return n;
    }
};
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestSumAfterKNegations = function(nums, k) {
    let negations = k
    let index = 0
    const sortedNums = [...nums]

    // Sort in increasing order
    sortedNums.sort((a, b) => a - b)

    // loop into the sorted array using the
    // number of negations
    while (negations > 0) {
        negations--

        const currentNumber = -sortedNums[index]
        const nextNumber = sortedNums[index + 1]

        sortedNums[index] = currentNumber

        // if the number is 0, undefined or
        // the current number is less than the
        // next number (meaning it will be
        // less the amount if it's a negative
        // number) just use the same number
        // again to flip.
        if (
                currentNumber === 0 ||
                nextNumber === undefined ||
                currentNumber < nextNumber
        ) continue

        index++
    }

    return sortedNums.reduce((sum, num) => sum + num, 0)
};
Maximize Sum Of Array After K Negations