Maximum product subset of an array

The problem, simply

You get a row of whole numbers. They can be positive, negative or zero. Choose some of them, at least one, and multiply the chosen ones together.

Give back the biggest product you can make.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every team. A team is a choice of yes or no for each card, so there are 2^n - 1 non-empty teams. Use the bits of a counter as the yes and no choices.

1. For mask from 1 to 2^n - 1, multiply the cards whose bit is on.
2. Keep the biggest product.

class Solution {
    public long maxProductSubset(int[] a) {
        int n = a.length;
        long best = Long.MIN_VALUE;
        for (int mask = 1; mask < (1 << n); mask++) {
            long product = 1;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) product *= a[i];  // card i is on the team
            }
            best = Math.max(best, product);
        }
        return best;
    }
}

How long it takes: 2^n teams, each multiplied in n steps, so O(2^n * n). Thirty cards is already a billion teams. Extra room: O(1).

Way 2: the clever way

You do not need to try teams. The best team follows simple rules:

1. Zeros never help, unless nothing else works. Leave them out.
2. Plus cards always help. Keep them all.
3. Minus cards help in pairs. If their count is odd, drop the one closest to zero, which is the biggest negative number.
4. Special cases: one card in total means the answer is that card. All zeros means 0. If after dropping nothing is left (one minus card plus zeros), the answer is 0.

So walk once to count minus cards and zeros and find the weakest minus card. Walk again to multiply everything except the zeros and that dropped card.

class Solution {
    public long maxProductSubset(int[] a) {
        int n = a.length;
        if (n == 1) return a[0];                  // must take the only card
        int minus = 0, zeros = 0, dropAt = -1;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0) zeros++;
            else if (a[i] < 0) {
                minus++;
                if (dropAt == -1 || a[i] > a[dropAt]) dropAt = i;  // closest to zero
            }
        }
        if (zeros == n) return 0;
        if (minus % 2 == 0) dropAt = -1;          // even: every minus card has a partner
        long product = 1;
        int used = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0 || i == dropAt) continue;
            product *= a[i];
            used++;
        }
        return used == 0 ? 0 : product;           // only a lone minus card and zeros were left
    }
}

How long it takes: two walks over the row, O(n). Extra room: a few counters, O(1).

Watch out for

• One minus card with only zeros, like [-1, 0, 0]: the answer is 0, not -1.
• A single card, like [-5]: the answer is -5. You cannot choose an empty team.
• The product overflows fast. Many versions ask for it modulo 10^9 + 7. Then you cannot divide out the dropped card, which is why the code skips it instead of dividing.
• Zeros do not break pairs. [-2, 0, -3] still gives 6.

What interviewers ask next

• Return the team, not only the product. Collect the cards the second walk multiplies, or a single zero in the special cases.
• What if the cards must be next to each other? That is the maximum product subarray. Keep the biggest and smallest product ending at each card, because a minus card swaps them.
• Smallest product instead? Make it negative if you can: with an odd count of minus cards keep them all, with an even count drop the weakest one, and keep all plus cards. If there are no minus cards, the answer is a zero if present, else the smallest plus card.
• Can you do it in one walk? Yes: multiply as you go and also track the weakest minus card, then divide it out at the end. That fails under a modulo, so two walks are safer.

Remember this

Grown-up words: the team is a subset, mood cards are signed numbers, the weakest minus card is the negative with the smallest absolute value, and the yes or no counter is a bitmask over subsets.