class Solution {
    public int largestSumAfterKNegations(int[] A, int K) {
        int k = K;
        int[] a = A;

        Arrays.sort(a);

        int i = 0;
        while (k > 0) {
            if (a[i] <= 0) {
                a[i] = -a[i];
                i++;
                k--;
            } else {
                break;
            }
        }

        int sum = 0;
        for (int aa : a) {
            sum += aa;
        }

        if (k % 2 == 1) {
            int min = 0;
            if(i > 0) {
                min = Math.min(a[i-1], a[i]);
                if (i < a.length - 1) {
                    min = Math.min(min, a[i + 1]);
                }
            } else {
                min = a[i];
            }
            sum = sum - 2*min;
        }

        return sum;
    }
}