Maximum Product Subarray (LeetCode 152)
You get an integer array nums. A subarray is a run of numbers that sit next to each other. Multiply the numbers of a subarray to get its product.
Find the subarray with the largest product and return that product. The array can hold negative numbers and zeros. The subarray must hold at least one number.
Worked Examples
nums = [2,3,-2,4]6[2, 3] has product 6. No other subarray is larger: -2 makes any run that holds it smaller, and [4] is only 4.nums = [-2,0,-1]0-2 and -1 have product 2, but they are not next to each other, so they are not a subarray. The best choice is [0], with product 0.⚖️Formal Constraints & Bounds
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10The product of any subarray of
numsfits in a 32-bit integer.
Core Insight
Multiplying by a negative number turns the smallest product into the largest one, so the best subarray ending at x comes from x alone, from the largest product extended by x, or from the smallest product extended by x: keep both ends for every position.
Real-World Scenario & Production Applications
Growth rates that multiply, such as a daily change of 1.02 or 0.97 in a price: the best stretch of days is the run with the largest product of factors, and one bad factor can be undone by another.
Step-by-Step Execution Trace Table
Trace of Example 1: nums = [2, 3, -2, 4]. hi, lo and best start at nums[0] = 2.
x | Candidates x, hi * x, lo * x | hi | lo | best |
|---|---|---|---|---|
| 3 | 3, 6, 6 | 6 | 3 | 6 |
| -2 | -2, -12, -6 | -2 | -12 | 6 |
| 4 | 4, -8, -48 | 4 | -48 | 6 |
At x = -2, the largest product ending here is -2 alone and the smallest is -12. A later negative number would turn -12 into the largest, which is why lo is kept.
| 1 | hi = lo = best = nums[0] |
| 2 | for x in nums[1:]: |
| 3 | hi, lo = max(x, hi * x, lo * x), min(x, hi * x, lo * x) |
| 4 | best = max(best, hi) |
| 5 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Kadane's Algorithm keeps one value per position: the best sum that ends here. For a product, one value is not enough. Multiplying by a negative number turns the smallest product into the largest one. So this variant keeps two values per position: hi, the largest product of a subarray that ends here, and lo, the smallest. Each new number x gives three candidates: x alone, hi * x and lo * x.
➗ What Is Added To Kadane
Kadane's Algorithm chooses between extending the run and starting fresh. This variant keeps that choice and adds one more piece of state, lo, because the worst product so far can become the best one after the next negative number.
🔑 The Key Idea in the Code
hi and lo are both computed from the old hi and the old lo, in one assignment. If hi is updated first, lo would be computed from the new hi, which is a different subarray.
Keeping only the largest product: with
curr = max(x, curr * x), a negativexmultiplies the largest product into a smaller one, and the smallest product that could turn positive is lost.[-2, 3, -4]returns 3 instead of 24.Updating
hibefore computinglo: afterhichanges,hi * xis a different subarray. Compute both in one assignment from the old values.Leaving
xout of the candidates: after a zero,hiandloare both 0 and onlyxalone can restart the run.[0, 2]returns 0 instead of 2.Starting
bestat 0: the subarray must hold at least one number, so an array of one negative number has a negative answer.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The largest product of a subarray": a best value over contiguous runs, like Kadane's Algorithm, but the operation is multiplication and the numbers may be negative. A negative number swaps the smallest and the largest, which tells you one running value is not enough.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
hi is the largest and lo is the smallest product of a subarray that ends at x. The next pair comes from three candidates: x alone, hi * x and lo * x. best keeps the largest hi.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Kadane's Algorithm and one extra piece of state. The best product ending at a number is not enough, because a negative number turns the smallest product into the largest. So I keep hi and lo, the largest and smallest product of a subarray ending at the current number. For each number x, the new hi is the maximum of x, hi times x and lo times x, and the new lo is the minimum of the same three values, both computed from the old hi and lo. Zeros restart the run automatically, because x alone is always a candidate. I keep the largest hi in best. That is one pass, order N time and order 1 space.
Complexity & Mathematical Proof
O(N)
Look at the loop. for x in nums[1:] visits each number once. Each visit computes three products, one max, one min and one comparison, which is constant work. That is N steps, so time is O(N).
O(1)
The code keeps three variables, hi, lo and best, whatever the length of nums is. There is no table and no recursion, so space is O(1).
Derivation Progression
for x in nums[1:] visits each number after the first once.
3 = O(1)
Three products, one max, one min and one comparison.
3N = O(N)
Numbers times a constant amount of work.
Variable Definitions
Length of nums
Largest product of a subarray that ends at the current number
Smallest product of a subarray that ends at the current number
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables hi, lo and best
O(1): one integer
Boundary Best / Worst Cases
: the loop always visits every number.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the largest product of a subarray", "negative numbers". It is a best value over contiguous runs, so this is Kadane's Algorithm, and the negative numbers mean it needs the smallest product as well.
and . A loop over all pairs is products; one pass is . The problem guarantees every product fits in 32 bits, so no overflow handling is needed here.
In a language with fixed-width integers, a product of many large numbers can overflow, which turns the smallest product into a large positive one. LeetCode guarantees the answer fits in 32 bits, but intermediate lo values of a run that is later discarded could be larger than that bound, so some solutions use a 64-bit type.
Maximum Product Subarray (LeetCode 152)
You get an integer array nums. A subarray is a run of numbers that sit next to each other. Multiply the numbers of a subarray to get its product.
Find the subarray with the largest product and return that product. The array can hold negative numbers and zeros. The subarray must hold at least one number.
Worked Examples
nums = [2,3,-2,4]6[2, 3] has product 6. No other subarray is larger: -2 makes any run that holds it smaller, and [4] is only 4.nums = [-2,0,-1]0-2 and -1 have product 2, but they are not next to each other, so they are not a subarray. The best choice is [0], with product 0.⚖️Formal Constraints & Bounds
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10The product of any subarray of
numsfits in a 32-bit integer.
Core Insight
Multiplying by a negative number turns the smallest product into the largest one, so the best subarray ending at x comes from x alone, from the largest product extended by x, or from the smallest product extended by x: keep both ends for every position.
Real-World Scenario & Production Applications
Growth rates that multiply, such as a daily change of 1.02 or 0.97 in a price: the best stretch of days is the run with the largest product of factors, and one bad factor can be undone by another.
Step-by-Step Execution Trace Table
Trace of Example 1: nums = [2, 3, -2, 4]. hi, lo and best start at nums[0] = 2.
x | Candidates x, hi * x, lo * x | hi | lo | best |
|---|---|---|---|---|
| 3 | 3, 6, 6 | 6 | 3 | 6 |
| -2 | -2, -12, -6 | -2 | -12 | 6 |
| 4 | 4, -8, -48 | 4 | -48 | 6 |
At x = -2, the largest product ending here is -2 alone and the smallest is -12. A later negative number would turn -12 into the largest, which is why lo is kept.
| 1 | hi = lo = best = nums[0] |
| 2 | for x in nums[1:]: |
| 3 | hi, lo = max(x, hi * x, lo * x), min(x, hi * x, lo * x) |
| 4 | best = max(best, hi) |
| 5 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Kadane's Algorithm keeps one value per position: the best sum that ends here. For a product, one value is not enough. Multiplying by a negative number turns the smallest product into the largest one. So this variant keeps two values per position: hi, the largest product of a subarray that ends here, and lo, the smallest. Each new number x gives three candidates: x alone, hi * x and lo * x.
➗ What Is Added To Kadane
Kadane's Algorithm chooses between extending the run and starting fresh. This variant keeps that choice and adds one more piece of state, lo, because the worst product so far can become the best one after the next negative number.
🔑 The Key Idea in the Code
hi and lo are both computed from the old hi and the old lo, in one assignment. If hi is updated first, lo would be computed from the new hi, which is a different subarray.
Keeping only the largest product: with
curr = max(x, curr * x), a negativexmultiplies the largest product into a smaller one, and the smallest product that could turn positive is lost.[-2, 3, -4]returns 3 instead of 24.Updating
hibefore computinglo: afterhichanges,hi * xis a different subarray. Compute both in one assignment from the old values.Leaving
xout of the candidates: after a zero,hiandloare both 0 and onlyxalone can restart the run.[0, 2]returns 0 instead of 2.Starting
bestat 0: the subarray must hold at least one number, so an array of one negative number has a negative answer.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The largest product of a subarray": a best value over contiguous runs, like Kadane's Algorithm, but the operation is multiplication and the numbers may be negative. A negative number swaps the smallest and the largest, which tells you one running value is not enough.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
hi is the largest and lo is the smallest product of a subarray that ends at x. The next pair comes from three candidates: x alone, hi * x and lo * x. best keeps the largest hi.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Kadane's Algorithm and one extra piece of state. The best product ending at a number is not enough, because a negative number turns the smallest product into the largest. So I keep hi and lo, the largest and smallest product of a subarray ending at the current number. For each number x, the new hi is the maximum of x, hi times x and lo times x, and the new lo is the minimum of the same three values, both computed from the old hi and lo. Zeros restart the run automatically, because x alone is always a candidate. I keep the largest hi in best. That is one pass, order N time and order 1 space.
Complexity & Mathematical Proof
O(N)
Look at the loop. for x in nums[1:] visits each number once. Each visit computes three products, one max, one min and one comparison, which is constant work. That is N steps, so time is O(N).
O(1)
The code keeps three variables, hi, lo and best, whatever the length of nums is. There is no table and no recursion, so space is O(1).
Derivation Progression
for x in nums[1:] visits each number after the first once.
3 = O(1)
Three products, one max, one min and one comparison.
3N = O(N)
Numbers times a constant amount of work.
Variable Definitions
Length of nums
Largest product of a subarray that ends at the current number
Smallest product of a subarray that ends at the current number
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables hi, lo and best
O(1): one integer
Boundary Best / Worst Cases
: the loop always visits every number.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the largest product of a subarray", "negative numbers". It is a best value over contiguous runs, so this is Kadane's Algorithm, and the negative numbers mean it needs the smallest product as well.
and . A loop over all pairs is products; one pass is . The problem guarantees every product fits in 32 bits, so no overflow handling is needed here.
In a language with fixed-width integers, a product of many large numbers can overflow, which turns the smallest product into a large positive one. LeetCode guarantees the answer fits in 32 bits, but intermediate lo values of a run that is later discarded could be larger than that bound, so some solutions use a 64-bit type.