Topics › Arrays › Hard

Maximum Product Subarray in an Array

Hard TUF ID 24 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a non-empty integer array nums. Find the contiguous subarray (at least one element) whose elements have the largest product, and return that product.

Constraints: 1 ≤ n ≤ 2 × 10^4, -10 ≤ nums[i] ≤ 10 on LeetCode, and the product of every subarray is guaranteed to fit in a 32-bit signed integer. That guarantee is what lets the running products below be exact.

Example 1

nums = [2, 3, -2, 4]
answer = 6

[2, 3] has product 6. Including -2 makes it negative, and [4] alone is only 4.

Example 2

nums = [-2, 0, -1]
answer = 0

Every subarray that avoids the zero is negative (-2, -1), so the zero itself is the best.

Example 3

nums = [-2, -3, 0, -4, -5]
answer = 20

The zero splits the array; [-4, -5] gives 20, better than [-2, -3] = 6.

Approach 1: Brute force

Intuition. For every starting index, extend the subarray to the right while multiplying into a running product, and record the best product seen. The running product saves re-multiplying from scratch, so this is O(n^2) rather than the O(n^3) of the fully naive version.

Algorithm.

1. For each i, set prod = 1.
2. For each j ≥ i, prod *= nums[j]; update best.
3. Return best.

static int bruteForce(int[] nums) {
    int n = nums.length;
    int best = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        long prod = 1;
        for (int j = i; j < n; j++) {
            prod *= nums[j];
            if (prod > best) best = (int) prod;
        }
    }
    return best;
}

Complexity. Time O(n^2). Space O(1).

prod is a long as a safety margin, but note that the problem’s guarantee is what keeps it meaningful: without the guarantee, products of 20000 values would overflow long long before the loop finished, and no fixed-width integer could represent them.

For n = 2 × 10^4 this is 2 × 10^8 multiplications, which passes on LeetCode but is not what the problem is testing.

Approach 2: Optimal, prefix and suffix products

Intuition. Think about which subarray can be the answer. Zeros are walls: no good subarray crosses a zero, so treat each zero-free stretch independently. Within such a stretch, every element is non-zero, so the product of the whole stretch is as large in absolute value as anything inside it. If that product is positive, the whole stretch is the answer for this segment. If it is negative, the stretch contains an odd number of negatives, and the best subarray drops either a prefix ending at the first negative or a suffix starting at the last negative. Either way, the optimal subarray is a prefix or a suffix of a zero-free stretch.

That observation becomes an algorithm: sweep once from the left accumulating a prefix product that resets to 1 after each zero, and simultaneously from the right accumulating a suffix product with the same reset rule. Every prefix and every suffix of every stretch is visited, and the maximum over all of them is the answer. The zero itself is also visited (prefix becomes 0 on that step), which covers inputs where 0 is the best possible.

Algorithm.

1. prefix = 1, suffix = 1, best = -infinity.
2. For i from 0 to n - 1:
   • If prefix == 0, reset it to 1; same for suffix.
   • prefix *= nums[i], suffix *= nums[n - 1 - i].
   • best = max(best, prefix, suffix).
3. Return best.

static int optimalPrefixSuffix(int[] nums) {
    int n = nums.length;
    int best = Integer.MIN_VALUE;
    long prefix = 1, suffix = 1;
    for (int i = 0; i < n; i++) {
        if (prefix == 0) prefix = 1;                       // a zero ended the previous run: start fresh
        if (suffix == 0) suffix = 1;
        prefix *= nums[i];                                 // product of nums[(last zero)+1 .. i]
        suffix *= nums[n - 1 - i];                         // product of nums[n-1-i .. (next zero)-1]
        best = (int) Math.max(best, Math.max(prefix, suffix));
    }
    return best;
}

Dry run on nums = [2, 3, -2, 4]:

The prefix [2, 3] with product 6 wins.

Complexity. Time O(n): one pass with two multiplications per step. Space O(1).

The reset must happen before multiplying by the current element, otherwise the step after a zero would still see 0 and the next stretch’s first element would never be counted on its own.

Approach 3: Optimal, carry the maximum and the minimum

Intuition. This is the product analogue of Kadane’s algorithm. For sums, the best subarray ending at i is either nums[i] alone or nums[i] extended from the best ending at i - 1. For products, a huge negative product can become the maximum after multiplying by a negative number, so a single running value is not enough. Carry two: curMax, the largest product of a subarray ending at i, and curMin, the smallest. Each new element either starts fresh or multiplies one of the two, and the sign flip is handled automatically because the three candidates x, curMax * x, curMin * x are all considered for both the new max and the new min.

Algorithm.

1. curMax = curMin = best = nums[0].
2. For each i ≥ 1 with x = nums[i]: compute a = curMax * x, b = curMin * x; set curMax = max(x, a, b), curMin = min(x, a, b), best = max(best, curMax).
3. Return best.

static int optimalMinMax(int[] nums) {
    int best = nums[0];
    long curMax = nums[0], curMin = nums[0];
    for (int i = 1; i < nums.length; i++) {
        long x = nums[i];
        long a = curMax * x, b = curMin * x;
        curMax = Math.max(x, Math.max(a, b));              // largest product of a subarray ending at i
        curMin = Math.min(x, Math.min(a, b));              // smallest product of a subarray ending at i
        best = (int) Math.max(best, curMax);
    }
    return best;
}

Dry run on nums = [-2, -3, 0, -4, -5]:

At i = 3 the largest product ending there is 0 (the subarray [0, -4]), while the smallest is -4 alone; it is that -4 which, multiplied by -5, produces the answer.

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

Both optimal methods are linear. The prefix/suffix one is easier to justify in an interview and needs only one state variable per direction; the min/max one generalises to streaming input (it never looks at the array from the right) and is the version most people recognise as “Kadane for products”.

Edge cases and pitfalls

• Single element. [-2] returns -2; the answer must be a non-empty subarray, so never initialise best to 0 or 1.
• Zeros. They split the array and may themselves be the answer ([-2, 0, -1] gives 0). Both optimal methods visit the zero as a candidate.
• Odd number of negatives. [2, -5, -2, -4, 3] is best without one end: -2 × -4 × 3 = 24. The prefix/suffix sweep finds it as a suffix; the min/max sweep rebuilds it after the first -5 turns curMin into -10.
• Overflow. Products grow fast. The methods multiply in long, which is exact under the problem’s guarantee that every subarray product fits an int; without that guarantee the problem is ill-posed for fixed-width integers.
• Integer.MIN_VALUE. [MIN_VALUE, 0, 3] returns 3. Casting Math.max(best, ...) back to int is safe because the maximum is always a valid subarray product.
• Resetting after zero in the wrong place. Resetting after the multiplication (instead of before) skips the first element of the next stretch as a standalone candidate.

Related problems

• Kadane’s Algorithm is the sum version that the min/max approach generalises.
• Print subarray with maximum subarray sum (extended version of above problem) shows how to recover the subarray itself from a Kadane sweep.
• Largest Subarray with Sum 0 is another problem where prefix aggregates over the array give an O(n) answer.