package com.fishercoder.solutions;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 1005. 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 <= A.length <= 10000
 * 1 <= K <= 10000
 * -100 <= A[i] <= 100
 * */
public class _1005 {
    public static class Solution1 {
        /**credit: 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> minHeap = new PriorityQueue<>();
            for (int num : A) {
                minHeap.offer(num);
            }
            while (K-- > 0) {
                minHeap.offer(-minHeap.poll());
            }
            int sum = 0;
            while (!minHeap.isEmpty()) {
                sum += minHeap.poll();
            }
            return sum;
        }
    }

    public static class Solution2 {
        /**credit: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252254/JavaC%2B%2BPython-Sort*/
        public int largestSumAfterKNegations(int[] A, int K) {
            Arrays.sort(A);
            for (int i = 0; i < A.length && K > 0 && A[i] < 0; i++, K--) {
                A[i] = -A[i];
            }
            int sum = 0;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < A.length; i++) {
                min = Math.min(min, A[i]);
                sum += A[i];
            }
            return K % 2 == 0 ? sum : sum - min * 2;
        }
    }
}

@@ -91,843 +91,8 @@
 e;%0A%0A
-/**%0A * 1005. Maximize Sum Of Array After K Negations%0A *%0A * Given an array A of integers, we must modify the array in the following way:%0A * we choose an i and replace A%5Bi%5D with -A%5Bi%5D, and we repeat this process K times in total.%0A * (We may choose the same index i multiple times.)%0A *%0A * Return the largest possible sum of the array after modifying it in this way.%0A *%0A * Example 1:%0A * Input: A = %5B4,2,3%5D, K = 1%0A * Output: 5%0A * Explanation: Choose indices (1,) and A becomes %5B4,-2,3%5D.%0A *%0A * Example 2:%0A * Input: A = %5B3,-1,0,2%5D, K = 3%0A * Output: 6%0A * Explanation: Choose indices (1, 2, 2) and A becomes %5B3,1,0,2%5D.%0A * Example 3:%0A *%0A * Input: A = %5B2,-3,-1,5,-4%5D, K = 2%0A * Output: 13%0A * Explanation: Choose indices (1, 4) and A becomes %5B2,3,-1,5,4%5D.%0A *%0A *%0A * Note:%0A *%0A * 1 %3C= A.length %3C= 10000%0A * 1 %3C= K %3C= 10000%0A * -100 %3C= A%5Bi%5D %3C= 100%0A * */%0A
 publ
@@ -147,32 +147,44 @@
 n1 %7B%0A        /**
+%0A         * 
 credit: https://
@@ -287,16 +287,26 @@
 solution
+%0A         
 */%0A     
@@ -812,16 +812,28 @@
      /**
+%0A         * 
 credit: 
@@ -939,16 +939,26 @@
 hon-Sort
+%0A         
 */%0A     

refactor 1005