Dynamic Programming · LC #152
Maximum Product Subarray
Track both the running maximum and minimum product at each element because a negative number can flip the min into the max. The global result is the max product seen across all positions.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an integer array `nums`, find the contiguous subarray that has the largest product and return that product.
Sample I/O
Input: nums = [2,3,-2,4] Output: 6 ([2,3]) Input: nums = [-2,0,-1] Output: 0
Intuition
How to Think About It
Intuition
A negative number flips max and min, so maintaining only the running max (as in Kadane's) loses information. By tracking both max and min simultaneously, a future negative element can convert the current minimum into a large positive product.
Core Concept
At each element n, new_max = max(n, maxP*n, minP*n) and new_min = min(n, maxP*n, minP*n). The global answer is the running maximum of maxP.
When to use
Contiguous subarray product problems, or any scenario where sign flips make tracking both extremes necessary.
When NOT to use
When the array contains only non-negative numbers - plain Kadane's suffices. Also not applicable when elements are non-contiguous (use subsequence DP instead).
Key Insights
What to Know Cold
- A negative number swaps the roles of maxP and minP, so always compute both from the same previous values before overwriting.
- A zero resets both maxP and minP to 0; subsequent elements start fresh.
- Initialise maxP, minP, and result all to nums[0] to handle single-element arrays correctly.
- Three-way candidate set {n, maxP*n, minP*n} handles all sign combinations.
- This is a DP variant: dp[i] depends only on dp[i-1], enabling O(1) space.
1 example
Worked Examples
Max product in mixed-sign array
Array [2,3,-2,4] - negatives break the product chain.
Track running max and min; update both before advancing.
Output: 6
Demonstrates why Kadane's algorithm must be extended for products: sign flips require tracking both extremes, a pattern that recurs in DP interviews at Amazon and Meta.