Maximize array sum after K negations

The problem, simply

You get a row of numbers and a number k. One move picks any number and flips its sign: 5 becomes -5, and -3 becomes 3. You must make exactly k moves. You may flip the same number more than once.

Give back the biggest total the row can have after all k moves.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do what the rules say, one stamp at a time. Each time, find the smallest card in the whole row and flip it. The smallest card is either the biggest frown, which is the best fix, or the smallest smile, which is the cheapest loss.

1. Repeat k times: scan the row for the smallest card and flip its sign.
2. Add up the row.

class Solution {
    public long maxSumAfterKFlips(int[] a, int k) {
        for (int step = 0; step < k; step++) {
            int min = 0;
            for (int j = 1; j < a.length; j++) {
                if (a[j] < a[min]) min = j;   // find the smallest card
            }
            a[min] = -a[min];                 // stamp it
        }
        long sum = 0;
        for (int x : a) sum += x;
        return sum;
    }
}

How long it takes: k stamps, and each stamp scans all n cards, so O(n * k). When k is a billion, this is far too slow. Extra room: nothing beyond a few counters, O(1).

Way 2: the clever way

Sort the cards once. Now the biggest frowns sit at the front, in order.

1. Sort the row from small to big.
2. Walk from the left. While the card is negative and stamps are left, flip it and use up one stamp.
3. Add up the row and remember the smallest card.
4. If an odd number of stamps is left, one stamp really hurts. Take it from the smallest card: subtract 2 * smallest. An even number of spare stamps cancels out, so ignore it.

The smallest card after the flips may be a card you just flipped. In the walkthrough, -1 becomes 1, and 1 is smaller than 2. That is why we look at the whole row, not only the card where we stopped.

import java.util.Arrays;

class Solution {
    public long maxSumAfterKFlips(int[] a, int k) {
        Arrays.sort(a);                          // biggest frowns come first
        for (int i = 0; i < a.length && k > 0 && a[i] < 0; i++) {
            a[i] = -a[i];                        // a frown becomes a smile
            k--;
        }
        long sum = 0;
        int smallest = Integer.MAX_VALUE;
        for (int x : a) {
            sum += x;
            smallest = Math.min(smallest, x);
        }
        if (k % 2 == 1) sum -= 2L * smallest;    // one spare flip: put it on the smallest card
        return sum;
    }
}

How long it takes: sorting is O(n log n) and the two walks are O(n), so O(n log n) in total, and k no longer matters. Extra room: O(1) beyond the sort.

Watch out for

• Exactly k or at most k? Read the problem. With at most k, you stop as soon as the negatives are gone and never pay for a spare flip.
• A zero in the row makes every spare flip free. The formula handles it, because smallest is 0.
• Use long for the sum. A row of large numbers overflows int.
• Flipping twice is the same as not flipping. Only the parity (odd or even) of the leftover k matters.

What interviewers ask next

• What if the numbers are small, like -100 to 100? Count how many times each value appears, then walk the counts from -100 upward. That is O(n + 201) with no sort.
• Can you use a heap instead? Put all cards in a min-heap, and k times pop the smallest, flip it and push it back. That is O(n + k log n), which is good when k is small.
• What if k is huge, like 10^9? The sorted way does not care. It only uses k % 2 after the negatives are fixed.
• Return the final row, not only the sum. Same steps, and flip a[index of smallest] instead of subtracting.

Remember this

Grown-up words: the cards are array elements, a flip is a negation, frowns are negative numbers, the stamps are the k operations, and odd or even leftover stamps is the parity of k.