152. Maximum Product Subarray¶
Edited by Charles
Medium · Python · Dynamic Programming
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return the product.
Original study notes follow, including intermediate snippets and earlier attempts.
Problem¶
Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return the product.
Example 1¶
Because:
has the maximum product:
Example 2¶
The result cannot be:
because:
is not a contiguous subarray.
This problem is similar to the Maximum Subarray problem, but multiplication introduces one important complication:
A negative number can turn the smallest negative product into the largest positive product.
Therefore, we cannot only keep track of the maximum product.
We need to maintain both the maximum and minimum product ending at each position.
Define:
and:
The key phrase is:
For example:
maxDp[1] represents the maximum product among all subarrays ending at nums[1] = 3:
Therefore:
This is the key idea of LeetCode 152.
Consider:
At 3, the minimum product ending there is:
So:
Now we encounter:
The previous minimum product:
multiplied by:
becomes:
which becomes the new maximum.
Therefore:
means that the previous minimum value may become the current maximum value.
Similarly, the previous maximum value may become the current minimum value.
So we must track:
at the same time.
At position i, any subarray ending at nums[i] has three possibilities.
Case 1 — Start a New Subarray¶
Ignore everything before i and start directly from:
The product is:
Case 2 — Extend the Previous Maximum Product¶
Take the previous maximum product:
and multiply by the current number:
Case 3 — Extend the Previous Minimum Product¶
Take the previous minimum product:
and multiply by:
So:
This case is especially important when nums[i] is negative.
Among the three possibilities:
take the maximum:
Similarly, take the minimum of the same three possibilities:
Therefore, the two transitions are:
minDp[i] = min(
maxDp[i - 1] * nums[i],
minDp[i - 1] * nums[i],
nums[i]
)
maxDp[i] = max(
maxDp[i - 1] * nums[i],
minDp[i - 1] * nums[i],
nums[i]
)
This is another important detail.
Why don't we only compare:
?
Because sometimes the best choice is to discard the previous subarray and start a new subarray from the current element.
For example:
At:
we have:
If we only extend the previous subarray:
But starting a new subarray gives:
Clearly:
Therefore:
must be one of the candidates.
Consider:
At:
all extended products become:
and starting from the current number also gives:
Therefore:
In this way, 0 naturally breaks the previous product chain.
We do not need any special handling for zero.
For the first element:
because there is only one non-empty subarray ending at index 0:
So both the maximum and minimum products are:
In the code:
The initial -inf values are overwritten as we process the array; the important initialization is:
Consider:
Initially:
So:
i = 1, nums[i] = 3¶
Three candidates:
Therefore:
Now:
i = 2, nums[i] = -2¶
Three candidates:
Therefore:
Now:
Notice how:
because the best subarray ending at index 2 is simply:
This does not mean the global answer has become -2.
The previous:
still has product:
i = 3, nums[i] = 4¶
Three candidates:
Therefore:
Final arrays:
Remember the definition:
The global maximum subarray does not necessarily end at the final position.
For:
we have:
The maximum product is:
which occurs at:
not:
Therefore, we return:
instead of:
For every nums[i]:
nums[i]
│
┌────────────┼────────────┐
↓ ↓ ↓
Start new Extend max Extend min
nums[i] maxDp[i-1] minDp[i-1]
× ×
nums[i] nums[i]
\ | /
\ | /
───────────────────────
│
three candidates
│
┌─────────┴─────────┐
↓ ↓
min() max()
↓ ↓
minDp[i] maxDp[i]
When:
we usually have:
But when:
multiplication reverses the order:
previous max × negative
↓
may become current minimum
previous min × negative
↓
may become current maximum
This is why LeetCode 152 requires two DP states.
A useful way to remember it is:
Addition:
large + something usually stays related to large
Multiplication:
negative numbers can flip max ↔ min
Time Complexity¶
We traverse the array once:
The final:
also takes O(n), so the total remains:
Space Complexity¶
We use two arrays of length n:
Therefore:
The space complexity can be optimized to O(1) because each state only depends on the previous position.
The most important state definitions are:
maxDp[i]
=
maximum product of a subarray ending exactly at i
minDp[i]
=
minimum product of a subarray ending exactly at i
At every position, there are three choices:
Therefore:
and:
The reason we need both maxDp and minDp is:
so:
Finally:
because:
and the global maximum does not necessarily end at the last position.
The core idea to remember:
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | September 18, 2026 |
Python solution¶
class Solution:
def maxProduct(self, nums: list[int]) -> int:
l = len(nums)
minDp = [-float('inf')] * l
maxDp = [-float('inf')] * l
minDp[0], maxDp[0] = nums[0], nums[0]
for i in range(1, l):
minDp[i] = min(
maxDp[i - 1] * nums[i],
minDp[i - 1] * nums[i],
nums[i]
)
maxDp[i] = max(
maxDp[i - 1] * nums[i],
minDp[i - 1] * nums[i],
nums[i]
)
return max(maxDp)