Maximum Product Subarray
Problem
Given an integer array nums, return the maximum product of a contiguous subarray within nums.
- 1 ≤ nums.length ≤ 2 * 10⁴
- −10 ≤ nums[i] ≤ 10
- The product of any prefix or suffix of nums fits in a 32-bit integer
Example
nums = [2,3,-2,4]6The subarray [2,3] has the maximum product 6. A brute-force approach would check all subarrays, calculating their products, which is inefficient. The key challenge is handling negative numbers, which can flip the sign of the product and thus affect the maximum product calculation. For example, the product of two negative numbers is positive, so tracking only the maximum product at each step is insufficient. The algorithm maintains both the current maximum and minimum products to capture this duality. At each iteration, it updates these values by considering the current number, the product of the current number with the previous maximum, and the product with the previous minimum. This ensures that the algorithm correctly handles sign changes and finds the global maximum product in a single pass.
Approach
Straightforward Solution
A brute-force approach would consider every possible subarray, compute its product, and track the maximum. This approach is O(n^2) and inefficient for large inputs.
Core Observation
The maximum product subarray problem requires tracking both the maximum and minimum products ending at each position because a negative number can turn a minimum product into a maximum product and vice versa.
Path to Optimal
PreviewThe key recognition signals are 'maximum product' and 'contiguous subarray' with the presence of negative numbers. These indicate a Dynamic Programming approach that tracks state at each position…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a single pass through the array, maintaining two variables: cur_max and cur_min, representing the maximum and minimum products ending at the current index…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm iterates through the array once, performing constant time operations at each step.
Space
O(1)
Only a fixed number of variables are used to track the current maximum, minimum, and result, regardless of input size.
Pattern Spotlight
Dynamic Programming (Tracking Dual States)
When the problem involves products with negative numbers, maintain both the maximum and minimum products at each step because a negative number can flip the sign, turning a minimum into a maximum and vice versa.
Solution
| 1 | class Solution:
|
| 2 | def maxProduct(self, nums: list[int]) -> int:
|
| 3 | if not nums:
|
| 4 | return 0
|
| 5 |
|
| 6 | res = nums[0]
|
| 7 | cur_min, cur_max = 1, 1
|
| 8 |
|
| 9 | for n in nums:
|
| 10 | temp_max_product = cur_max * n
|
| 11 |
|
| 12 | cur_max = max(n, temp_max_product, n * cur_min)
|
| 13 | cur_min = min(n, temp_max_product, n * cur_min)
|
| 14 |
|
| 15 | res = max(res, cur_max)
|
| 16 |
|
| 17 | return res |
Step-by-Step Solution
Handle Empty Input Edge Case to Avoid Errors
| 3 | if not nums:
|
| 4 | return 0
|
Objective
To immediately return 0 if the input array is empty, preventing errors in subsequent logic.
Key Insight
An empty input means no subarray exists, so the maximum product is trivially 0. Handling this edge case upfront avoids unnecessary computation and potential runtime errors.
Interview Quick-Check
State & Boundaries
Check for empty input to handle edge cases where no subarray exists.
Initialize Tracking Variables for Maximum Product Calculation
To set up variables that track the global maximum product and the current maximum and minimum products ending at each position.
Iterate Through the Array Updating Maximum and Minimum Products
To update the current maximum and minimum products at each step by considering the current number and its products with previous max and min, and update the global maximum accordingly.
Return the Global Maximum Product Found
To return the maximum product of any contiguous subarray found during iteration.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
cur_max = max(n, temp_max_product, n * cur_min)Update the current maximum product by taking the maximum of the current number, the product of the current number and previous maximum, and the product of the current number and previous minimum.
This line is the heart of the algorithm; it simultaneously considers the current number and its products with previous max and min to correctly handle sign changes and identify the maximum product subarray ending at the current index.
cur_min = min(n, temp_max_product, n * cur_min)Update the current minimum product by taking the minimum of the current number, the product of the current number and previous maximum, and the product of the current number and previous minimum.
This line complements the max update by tracking the minimum product, enabling the algorithm to capture potential sign flips that can turn a small negative product into a large positive product.
Full line-by-line criticality + rationale for all 10 lines available on Pro.
Test Your Understanding
Why must the algorithm track both the current maximum and minimum products at each step?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Maximum Product Subarray from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Maximum Product Subarray drill