Algorithm

Maximum Product Subarray

Arrays & Strings Pattern

Maximum Product Subarray

Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return the product.

CONSTRAINTS
  • 1 <= nums.length <= 2 × 10⁴
  • -10 <= nums[i] <= 10
  • The product of any subarray of nums is guaranteed to fit in a 32-bit integer
EXAMPLE 1
Input: nums = [2,3,-2,4]
Output: 6
[2, 3] gives 6. Extending across the -2 flips the product negative, and 4 alone cannot beat 6.
EXAMPLE 2
Input: nums = [-2,0,-1]
Output: 0
Every window either contains the zero (product 0) or is stuck negative. The single-element window [0] achieves the best possible: 0.
EXAMPLE 3
Input: nums = [-2,3,-4]
Output: 24
The two negatives cancel: (-2) × 3 × (-4) = 24. Taking the whole array wins.
EXAMPLE 4
Input: nums = [-2]
Output: -2
Only one non-empty subarray exists. The answer can be negative when nothing better is available.
Does 'subarray' mean contiguous here too?
Yes — an unbroken slice with at least one element, same definition as in Maximum Subarray.
Can the answer be negative?
Yes. The subarray must be non-empty, so nums = [-2] returns -2. (Though if the array contains any zero, the answer is never below 0 — the window holding just that zero already achieves 0.)
Should I worry about the product overflowing?
Excellent question to ask — products explode far faster than sums. Here the constraints promise every subarray product fits in a 32-bit integer, so no special handling is needed. Without that promise you would raise it: a wider integer type, or discussing bounds with the interviewer.
What happens at a zero?
Every window containing it multiplies to 0, so both trackers honestly become 0 there (and 0 is recorded as a candidate answer). The next step's max(num, ...) choice then starts a fresh streak — zeros split the array into independent segments with no extra code.

Finding the maximum product subarray means identifying a contiguous sequence of numbers that, when multiplied together, yield the largest possible value. Unlike summation, products are highly sensitive to zeros and negative numbers, which can instantly flip a result from very small to very large.

Quadratic Products (O(N²))

The simplest approach is to calculate the product of every possible subarray. We use two loops to define the window and keep a running product for each start point.

python
res = nums[0]
for i in range(len(nums)):
    current_prod = 1
    for j in range(i, len(nums)):
        current_prod *= nums[j]
        res = max(res, current_prod)
return res
The Flipping Problem

We might try to apply basic Kadane's Algorithm (which works for sums). However, products are different because negative numbers flip results. In a sum, a huge negative number is always bad. In a product, a huge negative number is a "potential maximum" because multiplying it by another negative number could instantly make it the largest value in the array. This means tracking only the "best so far" is not enough.

Dual Tracking (O(N))

Instead of checking all windows, we walk through the array exactly once while tracking two values: the current maximum AND the current minimum.
- When we hit a negative number, the max and min swap roles.
- This ensures we never "lose" a large negative buffer that could become our new maximum later.

python
max_p = min_p = result = nums[0]
for i in range(1, len(nums)):
    num = nums[i]
    if num < 0:
        max_p, min_p = min_p, max_p # Roles swap
    
    max_p = max(num, num * max_p)
    min_p = min(num, num * min_p)
    result = max(result, max_p)
return result
Worked Example:[2, 3, -2, 4]
0
2
num
1
3
2
-2
3
4
We initialize our tracking values with the first element 2: the current maximum product is 2, the current minimum product is 2, and our overall max product is 2.
0
2
1
3
num
2
-2
3
4
We process the number 3. We compute the new maximum product as 6 (3 times 2) and the new minimum as 3. Our overall maximum product rises to 6.
0
2
1
3
2
-2
num
3
4
We encounter the negative number -2. Because multiplying by a negative flips our values, we swap our tracking maximum and minimum. Our new maximum product becomes -2, and our new minimum becomes -12. The overall max product remains 6.
0
2
1
3
2
-2
3
4
num
We process the number 4. Our current maximum product becomes 4 (4 times -1 is less than 4), and our running minimum drops to -48. The overall maximum product remains 6, which is our final answer.
Interactive Strategy Visualization

The Sign Flipper

Record Max: 2
2
3
-2
4
-2
Positive High
2
Negative Low
2
Starting with 2. Max and Min both begin here.
INSIGHT

Negatives are risky but valuable. They can turn the worst min into the best max instantly.

EFFICIENCY

We find the record in one single pass by keeping track of both extremes at every step.

O(N²) Brute Force
→
O(N) Max & Min Tracking