AlgoMaster Logo

Maximum Product Subarray

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

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

This problem resembles Maximum Subarray (Kadane's algorithm), but negative numbers change the reasoning. With sums, a negative number always lowers the running total. With products, a negative number can produce the best result if it later meets another negative number. The product of two negatives is positive, so the most negative product seen so far can become the largest product after one more multiplication.

Zeros add a second complication. Any subarray containing a zero has a product of zero, which resets the running product. The problem therefore involves three kinds of values: positive numbers that grow the product, negative numbers that flip its sign, and zeros that reset it to zero.

Key Constraints:

  • nums.length <= 2 * 10^4 → An O(n^2) solution passes within the time limit, and O(n) is the target.
  • The problem guarantees every subarray product fits in a 32-bit integer, so a plain int holds intermediate products without overflow.

Approach 1: Brute Force

Intuition

Check every possible subarray, compute its product, and keep the largest. For each starting index i, extend the subarray to the right one element at a time, multiplying as you go. This produces the product of every subarray that starts at i without recomputing from scratch for each ending point.

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

The next approach processes each element once, tracking enough information at each position to determine the maximum product of a subarray ending there. This brings the time down to O(n).

Approach 2: Dynamic Programming (Track Min and Max)

Intuition

For Maximum Subarray Sum, Kadane's algorithm works: at each position, the maximum sum ending there is either the current element alone or the current element plus the previous maximum sum.

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 as much as the maximum. The solution tracks both the maximum and the minimum product ending at each position.

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

A different O(n) approach reaches the same answer with a single insight about negatives and zeros, computing running products from both ends of the array.

Approach 3: Prefix-Suffix Product

Intuition

Consider the array split into segments separated by zeros, since any subarray spanning a zero has product zero. Within one zero-free segment, if the count of negative numbers is even, the product of the entire segment is positive and is the maximum for that segment. If the count is odd, the optimal subarray drops everything up to and including one of the negatives: either the leftmost negative and everything before it, or the rightmost negative and everything after it.

Both cases reduce to the same computation. Take a prefix product (left to right) and a suffix product (right to left), resetting each to 1 after a zero, and track the maximum value either product reaches.

This covers every optimal subarray. The optimal subarray within a segment is either the whole segment (even negatives) or one of the two segment-anchored pieces above (odd negatives). The prefix product, accumulated from the left edge of a segment, takes the value of every subarray that starts at that left edge, which includes the piece ending just before the rightmost negative. The suffix product does the same from the right edge, which includes the piece starting just after the leftmost negative. The maximum across both passes therefore includes the optimal subarray of every segment.

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