AlgoMaster Logo

Maximum Product Subarray

Last Updated: March 22, 2026

medium
5 min read

Understanding the Problem

We need to find a contiguous subarray within nums whose elements multiply together to give the largest possible product.

This problem looks a lot like Maximum Subarray (Kadane's algorithm), but there's a twist that makes it trickier: negative numbers. With sums, a negative number is always bad. With products, a negative number can become your best friend if it meets another negative number down the road. The product of two negatives is positive, so the smallest (most negative) product so far could suddenly become the largest product after one multiplication.

Zeros add another wrinkle. Any subarray containing a zero has a product of zero, which effectively resets everything. So the problem breaks down into reasoning about three things: positive numbers that grow the product, negative numbers that flip the sign, and zeros that kill the product entirely.

Key Constraints:

  • nums.length <= 2 * 10^4 → An O(n^2) solution should pass comfortably, and O(n) is ideal
  • -10 <= nums[i] <= 10 → Values are small, so individual multiplications won't overflow, but subarray products can grow (the problem guarantees they fit in a 32-bit integer)

Approach 1: Brute Force

Intuition

The most straightforward approach is to check every possible subarray, compute its product, and keep track of the largest one. For each starting index i, we extend the subarray to the right one element at a time, multiplying as we go. This gives us the product of every subarray without recalculating from scratch each time.

Algorithm

  1. Initialize maxProduct to the first element of the array (handles the single-element case).
  2. For each starting index i from 0 to n-1:
    • Set currentProduct = 1.
    • For each ending index j from i to n-1:
      • Multiply currentProduct by nums[j].
      • Update maxProduct if currentProduct is larger.
  3. Return maxProduct.

Example Walkthrough

1i=0, j=0: product=2, maxProduct=2
0
i
2
j
1
3
2
-2
3
4
1/11

Code

For each starting index, we scan forward through the rest of the array to compute every subarray product. What if we could process each element just once, keeping track of enough information at each position to determine the maximum product ending there?

Approach 2: Dynamic Programming (Track Min and Max)

Intuition

If this were Maximum Subarray Sum, we'd use Kadane's algorithm: at each position, the maximum sum ending here is either the current element alone or the current element plus the previous maximum sum. Simple.

But products behave differently. A large negative product times a negative number becomes a large positive product. So the minimum product at the previous position matters just as much as the maximum. Here's the key insight: at each position, track both the maximum and minimum product ending there.

At each element nums[i], the maximum product ending at position i is the largest of three candidates:

  • nums[i] alone (start a fresh subarray)
  • maxSoFar * nums[i] (extend the previous best)
  • minSoFar * nums[i] (a negative times a negative might be the new best)

The minimum product ending at position i follows the same logic but takes the smallest of the three. We need the minimum because it might become the maximum at the next step if we hit another negative number.

Algorithm

  1. Initialize maxSoFar, minSoFar, and result to nums[0].
  2. Iterate through the array starting from index 1:
    • Compute tempMax = max(nums[i], maxSoFar * nums[i], minSoFar * nums[i]).
    • Compute tempMin = min(nums[i], maxSoFar * nums[i], minSoFar * nums[i]).
    • Update maxSoFar = tempMax and minSoFar = tempMin.
    • Update result = max(result, maxSoFar).
  3. Return result.

Note: We compute both tempMax and tempMin before updating either one, because updating maxSoFar first would corrupt the calculation of minSoFar.

Example Walkthrough

1Init: maxSoFar=2, minSoFar=2, result=2
0
2
1
3
2
-2
3
4
1/5

Code

This approach is optimal in time, but there's an alternative O(n) approach that uses a different insight and can be easier to reason about in interviews. What if we just computed products from both ends of the array and took the maximum?

Approach 3: Prefix-Suffix Product

Intuition

Here's a completely different way to think about it. Consider the array without any zeros. If the array has an even number of negative numbers, the answer is the product of the entire array (all negatives cancel out). If it has an odd number of negatives, the answer is the larger of two options: drop the leftmost negative and everything before it, or drop the rightmost negative and everything after it.

This leads to a clean approach: compute prefix products (left to right) and suffix products (right to left), and the answer is the maximum across all of them. When we hit a zero, we reset the running product to 1, because zero splits the array into independent segments.

Why does this work? The maximum product subarray must start from the left end of some segment or end at the right end of some segment (where segments are separated by zeros). The prefix pass catches subarrays anchored to the left, and the suffix pass catches subarrays anchored to the right. Between the two passes, we cover every optimal subarray.

Algorithm

  1. Initialize result to the first element, prefix = 0, and suffix = 0.
  2. Iterate through the array from left to right:
    • If prefix is 0, reset it to 1 (start a new segment).
    • Multiply prefix by nums[i].
    • If suffix is 0, reset it to 1.
    • Multiply suffix by nums[n - 1 - i] (building the product from the right).
    • Update result = max(result, prefix, suffix).
  3. Return result.

Example Walkthrough

1Init: result=2, prefix=0, suffix=0
0
2
1
3
2
-2
3
4
1/6

Code