@@ -0,0 +1,2424 @@
+package array;%0A%0Aimport java.util.Arrays;%0A%0Apublic class Q1005MaximizeSumOfArrayAfterKNegations %7B%0A%0A    //Difficulty: easy%0A    //TAG: array%0A%0A    /**%0A     * 1005. Maximize Sum Of Array After K Negations%0A     * Given an array A of integers, we must modify the array in the following way: we choose an i and replace A%5Bi%5D with -A%5Bi%5D, and we repeat this process K times in total.  (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     *%0A     *%0A     * Example 1:%0A     *%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     * Example 2:%0A     *%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%0A    /*%0A    Solution:%0A    Sort the array then we are easy flip num %3C 0%0A    Try to flip all num %3C 0 once and add to sum, cases after this step:%0A    1. K == 0 and few more num %3C 0%0A        add all to sum and return%0A    2. K %25 2 == 0, we could flip even number of any numbers, and all nums %3E 0%0A        add all to sum%0A    3. K %25 2 == 1, we need find a number and make it %3C 0, which we find the min in array%0A        sum -= 2 * min after add all%0A%0A    Time: O(nlogn + n)%0A     */%0A%0A    public int largestSumAfterKNegations(int%5B%5D A, int K) %7B%0A        if (A == null %7C%7C A.length == 0) return 0;%0A        Arrays.sort(A);%0A        int index = 0, sum = 0, min = Math.abs(A%5B0%5D);%0A        //add max K numbers in positive flip%0A        while (index %3C A.length && A%5Bindex%5D %3C 0 && K %3E 0) %7B%0A            sum += Math.abs(A%5Bindex%5D);%0A            min = Math.min(min, Math.abs(A%5Bindex%5D));%0A            index++;%0A            K--;%0A        %7D%0A        //try to add all rest numbers (no matter %3C or %3E 0), find min in the array%0A        while (index %3C A.length) %7B%0A            sum += A%5Bindex%5D;%0A            min = Math.min(min, Math.abs(A%5Bindex%5D));%0A            index++;%0A        %7D%0A        //If we need flip one positive number, then we already add all to sum, we need sum - 2 * min%0A        if (K %25 2 != 0) %7B%0A            sum -= 2 * min;%0A        %7D%0A        return sum;%0A    %7D%0A%0A%7D%0A

1005. Maximize Sum Of Array After K Negations