← DSA Atlas
Dedicated problem page · #152

Maximum Product Subarray

MediumOne-Dimensional Dynamic ProgrammingTrack running max and min1-D dynamic programming (running extremes)
Solve on LeetCode ↗
152
MediumOne-Dimensional Dynamic Programming1-D dynamic programming (running extremes)Track running max and min

Maximum Product Subarray

Given an integer array nums, find the contiguous non-empty subarray with the largest product and return that product. The answer fits in a 32-bit integer.

Open official problem prompt ↗
In plain English

Find the single largest product achievable by any contiguous run of numbers.

Picture it like this

Tracking your best and worst account balances as you walk a street of multipliers: a sudden negative can turn your deepest loss into your biggest gain.

Example
Input
nums = [2, 3, -2, 4]
Output
6
Why
The subarray [2, 3] has product 6, the largest over all contiguous subarrays.
Constraints
1 <= nums.length <= 2 * 10^4-10 <= nums[i] <= 10The product of any subarray is guaranteed to fit in a 32-bit integer
Pattern lesson

See the pattern, then code

Track running max and min
Recognition clue

Maximum contiguous product where negatives flip sign - you need to carry both the largest and smallest products so a future negative can turn the min into the max.

↗
One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. Because a negative number swaps largest and smallest, maintain both cur_max and cur_min ending at the current index; the new max is the best of the element alone or the element times a prior extreme.

New words, made simpleKnow these before the algorithm
cur_max
Largest product of a subarray ending exactly at the current index.
cur_min
Smallest (most negative) product ending here, kept because a negative can flip it to the max.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
All subarrays

Too slow for 20k elements and redundant.

Compute the product of every start-end pair.

Time O(n^2)Space O(1)
Best choiceRolling max/min DP

Handles sign flips in one pass; the intended solution.

Carry both extremes ending at i, swapping on negatives.

Time O(n)Space O(1)
The rule we keep true

Invariant

After index i, cur_max and cur_min are the largest and smallest products of any subarray ending at i.

Why this is correct

Reasoning

A subarray ending at i either is nums[i] alone or extends the best/worst subarray ending at i-1; multiplying by a negative exchanges which extreme is largest, so swapping first keeps both invariants correct.

The algorithm in three movesSay these aloud before coding
1Initialize res, cur_max, cur_min to nums[0]

x=3: cur_max=6, cur_min=3, res=6

2For each later element, if it is negative swap cur_max and cur_min

x=-2: swap -> cur_max=-2, cur_min=-12, res=6

3Set cur_max = max(x, cur_max * x)

x=4: cur_max=4, cur_min=-48, res=6

4Set cur_min = min(x, cur_min * x)

5Update res with cur_max

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
20
31
-22
43
1 · Readnums[0]=2
2 · AskSeed the extremes
3 · Update stateres=cur_max=cur_min=2
4 · ResultStart at 2.
Key takeaway

The best product 6 comes from the [2,3] window before the negative resets the running max.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Seed with first element

    A subarray must be non-empty, so all three start at nums[0].

  2. 2
    Lines 5-6Swap on negatives

    A negative multiplier turns the smallest product into the largest, so exchange them before combining.

  3. 3
    Lines 7-8Update both extremes

    Each is either the element alone (restart) or the element times the prior extreme (extend).

  4. 4
    Lines 9Track the global best

    res records the maximum cur_max seen so far.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single element array returns that element
  • Zeros reset both extremes since max/min with x=0 restarts
  • All negatives, e.g. [-2,-3,-4], where the best comes from an even count
  • The answer can be a single negative when every product is negative
!

Common beginner mistakes

  • Forgetting to keep the running minimum, so a later negative cannot recover a large product
  • Swapping after multiplying instead of before
  • Assuming zeros can be ignored rather than restarting the window
Check your understanding

Why track the minimum product at all?

More in One-Dimensional Dynamic Programming

#198House RobberTake-or-skip linear DP#322Coin ChangeUnbounded knapsack (min coins)#300Longest Increasing SubsequencePatience sorting (tails array)#5Longest Palindromic SubstringExpand around center#32Longest Valid ParenthesesIndex stack with sentinel base#70Climbing StairsFibonacci-style linear DP