LeetCode 1005 - Maximize Sum Of Array After K Negations

https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/

Given an array A of integers, we must modify the array in the following way: we choose an i and replace A[i] with -A[i], and we repeat this process K times in total.  (We may choose the same index i multiple times.)

Return the largest possible sum of the array after modifying it in this way.

Example 1:

Input: A = [4,2,3], K = 1
Output: 5
Explanation: Choose indices (1,) and A becomes [4,-2,3].

Example 2:

Input: A = [3,-1,0,2], K = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].

Example 3:

Input: A = [2,-3,-1,5,-4], K = 2
Output: 13
Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].

Note:

1. 1 <= A.length <= 10000
2. 1 <= K <= 10000
3. -100 <= A[i] <= 100

https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252254/C%2B%2BPython-Sort
We can improve this to O(N) by quick selecting the Kth in the negative numbers.

    public int largestSumAfterKNegations(int[] A, int K) {
        Arrays.sort(A);
        for (int i = 0; K > 0 && i < A.length && A[i] < 0; ++i, --K)
            A[i] = -A[i];
        int res = 0, min = Integer.MAX_VALUE;
        for (int a : A) {
            res += a;
            min = Math.min(min, a);
        }
        return res - (K % 2) * min * 2;
    }

https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252520/Java-solution-O(1)-space-one-pass.

Traverse the array, track the number of negative elements
If number of negative elements is smaller than K, we can flip it to positive, otherwise, keep it as negative.
After the traversal, if we still have K - count flips to finish, it means we have flipped all negative elements, and have to touch a positive element. if K - count is even, flip any element is ok since it does not change anything. If K - count is odd, choose the smallest element which we have kept tracking in the traversal by minPositive.

        Arrays.sort(A);
        int count = 0, sum = 0, minPositive = Integer.MAX_VALUE;
        for (int num : A) {
            if (num < 0 && ++count <= K) {
                num = -num;
            }
            sum += num;
            minPositive = Math.min(minPositive, num);
        }
        if (count > K || (K - count) % 2 == 0) {
            return sum;
        } else {
            return sum - minPositive * 2;
        }

X. 
https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252228/A-very-simple-java-solution

    public int largestSumAfterKNegations(int[] A, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        
        for(int x: A) pq.add(x);
        while( K--  > 0) pq.add(-pq.poll());
  
        int sum  = 0;
        for(int i = 0; i < A.length; i++){
            sum += pq.poll();
        }
        return sum;
    }