Maximum Product Subarray

Given an array of integers (positive, negative, or zero), find the contiguous non-empty subarray with the largest product, and return the product.

LeetCode: 152. Maximum Product Subarray

Example

Text

[2, 3, -2, 4]   ->  6    ([2, 3])
[-2, 0, -1]     ->  0    ([0])
[-2, 3, -4]     ->  24   (the whole array: two negatives)

Brute force: every subarray

Fix a start, extend the end one element at a time, and keep a running product.

Java

public class Main {
    static long maxProduct(long[] nums) {
        long best = Long.MIN_VALUE;
        for (int start = 0; start < nums.length; start++) {
            long product = 1;
            for (int end = start; end < nums.length; end++) {
                product *= nums[end];
                best = Math.max(best, product);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxProduct(new long[]{2, 3, -2, 4}) + " " + maxProduct(new long[]{-2, 0, -1}) + " " + maxProduct(new long[]{-2, 3, -4}));
    }
}

Output

6 0 24

Time: O(n²). Space: O(1).

Optimal: track the largest and smallest product

This looks like Kadane's algorithm, but with a twist: multiplying by a negative number turns the smallest product into the largest. So keep both the largest (hi) and the smallest (lo) product of a subarray ending at the current index. For the next element x, the new extremes are among:

x alone (start a new subarray),
hi * x,
lo * x (a very negative product times a negative x).

x	2	3	-2	4
hi	2	6	-2	4
lo	2	3	-12	-48
best	2	6	6	6

Java

public class Main {
    static long maxProduct(long[] nums) {
        long hi = nums[0], lo = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            long x = nums[i];
            long a = hi * x, b = lo * x;
            hi = Math.max(x, Math.max(a, b));
            lo = Math.min(x, Math.min(a, b));
            best = Math.max(best, hi);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxProduct(new long[]{2, 3, -2, 4}) + " " + maxProduct(new long[]{-2, 0, -1}) + " " + maxProduct(new long[]{-2, 3, -4}));
        System.out.println(maxProduct(new long[]{-3}) + " " + maxProduct(new long[]{-1, -2, -3, 0, 5}));
    }
}

Output

6 0 24
-3 6

Time: O(n). Space: O(1).

Both new values are computed from the old hi and lo, which is why a and b are computed before either hi or lo is overwritten.

Edge cases

Zeros: reset both hi and lo to 0, and the next element starts fresh (x alone wins).
A single negative element: the answer is that element.
Overflow: products grow quickly. The examples use long, which wraps silently on overflow. Use BigInteger or Math.multiplyExact (which throws ArithmeticException) if the constraints allow long runs of large values.