Find maximum product subarray

The problem, simply

You get an array of whole numbers: positive, negative or zero. Pick a stretch of boxes next to each other (at least one box) and multiply them. Give back the biggest product any stretch can make.

It looks like the biggest sum problem, but multiplying is sneakier. A very negative product can become a very big one if one more negative number comes along.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every start, and grow the stretch to the right one box at a time, multiplying as you go.

1. For each start i, set product = 1.
2. For each end j >= i, multiply by arr[j] and update best.

class Solution {
    public int maxProduct(int[] arr) {
        long best = Long.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            long product = 1;
            for (int j = i; j < arr.length; j++) {
                product *= arr[j];                 // grow the stretch by one box
                best = Math.max(best, product);
            }
        }
        return (int) best;
    }
}

How long it takes: about n * n / 2 stretches, O(n^2). Extra room: two numbers, O(1). Keeping a running product is what makes it O(n^2) and not O(n^3): each longer stretch costs one multiplication.

Way 2: the clever way

For the stretch that ends at box i, keep two numbers:

• big: the biggest product of a stretch ending here.
• small: the smallest (most negative) product of a stretch ending here.

At the next box x, the new stretch ending there is one of three things: x alone, big * x, or small * x. The new big is the largest of the three and the new small is the smallest. If x is negative, small * x can become the new biggest.

1. big = small = best = arr[0].
2. For each next x: compute the three choices, set big and small (use the old values for both).
3. best = max(best, big).

The animation shows both stretches: the one that makes big and the one that makes small.

class Solution {
    public int maxProduct(int[] arr) {
        int big = arr[0], small = arr[0], best = arr[0];
        for (int i = 1; i < arr.length; i++) {
            int x = arr[i];
            int a = x, b = big * x, c = small * x;    // alone, after big, after small
            big = Math.max(a, Math.max(b, c));
            small = Math.min(a, Math.min(b, c));      // uses the old big through b
            best = Math.max(best, big);
        }
        return best;
    }
}

How long it takes: one walk, O(n). Extra room: three numbers, O(1).

A zero needs no special code: at a zero, both big and small become 0, and the next box can start fresh because "x alone" is always one of the choices.

Watch out for

• Products grow very fast. If the numbers can be large, use long, or double if only comparing.
• Forgetting the "x alone" choice breaks the restart after a zero.
• Tracking only the biggest, like Kadane's sum trick, fails on [2, 3, -2, 4, -1]: it never sees -48 turning into 48.

What interviewers ask next

• Another O(n) way? Multiply from the left and from the right, resetting to 1 after a zero, and take the biggest product seen in either pass. With an odd number of negatives, the best stretch drops either the first or the last negative, and one of the two passes finds it.
• Return the stretch too? Track where the big and small stretches start, like the animation does.
• Longest stretch with a positive product? Same two number idea, but carry lengths: the length of the longest stretch ending here with a positive product, and with a negative product.
• Count stretches with product less than k (all positive numbers)? A sliding window: grow the right end, and shrink the left end while the product is too big.

Remember this

Grown-up words: the flip stone is a negative number changing sign, carrying two best values per position is a small dynamic programming with two states, and it is the product version of Kadane's algorithm.