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
The 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. The insight is to maintain two running values: the maximum and minimum products ending at the current index. This dual tracking handles sign flips caused by negative numbers. At each step, the algorithm updates these values by considering the current number alone, the product with the previous maximum, and the product with the previous minimum. This approach reduces the problem to a single pass with O(n) time complexity.
Optimal Approach
Use 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. For each number, compute the possible candidates (current number, current number times cur_max, current number times cur_min), update cur_max and cur_min accordingly, and track the global maximum product found so far. This approach correctly handles negative numbers and zeros, ensuring the maximum product subarray is found efficiently.
Time
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
| 6 | res = nums[0]
|
| 7 | cur_min, cur_max = 1, 1
|
Objective
To set up variables that track the global maximum product and the current maximum and minimum products ending at each position.
Key Insight
Initializing res to the first element ensures the result starts with a valid subarray product. Setting cur_max and cur_min to 1 prepares for multiplication without affecting the first iteration. These variables enable the algorithm to track the best and worst products dynamically as it iterates through the array.
Interview Quick-Check
Core Logic
Initialize res with the first element to handle arrays with a single element correctly.
Common Pitfalls & Bugs
Starting cur_max and cur_min at 1 avoids incorrect multiplication results in the first iteration.
Iterate Through the Array Updating Maximum and Minimum Products
| 9 | for n in nums:
|
| 10 | temp_max_product = cur_max * n
|
| 12 | cur_max = max(n, temp_max_product, n * cur_min)
|
| 13 | cur_min = min(n, temp_max_product, n * cur_min)
|
| 15 | res = max(res, cur_max)
|
Objective
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.
Key Insight
At each iteration, the algorithm considers three candidates for both the current maximum and minimum products: the current number alone, the product of the current number with the previous maximum, and the product with the previous minimum. This accounts for the possibility that a negative number flips the sign, turning a minimum into a maximum and vice versa. Updating res with the current maximum ensures the global maximum product is tracked throughout the iteration.
Interview Quick-Check
Core Logic
Maintain both cur_max and cur_min to handle sign changes caused by negative numbers, updating them by considering the current number and its products with previous cur_max and cur_min.
State & Boundaries
Update res with the maximum of itself and cur_max to track the global maximum product.
Common Pitfalls & Bugs
Failing to consider the product with cur_min can miss cases where two negatives produce a larger positive product.
Return the Global Maximum Product Found
| 17 | return res |
Objective
To return the maximum product of any contiguous subarray found during iteration.
Key Insight
After processing all elements, res holds the maximum product subarray value. Returning it completes the algorithm and provides the correct answer.
Interview Quick-Check
Core Logic
Return the tracked global maximum product after processing all elements.
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.
res = nums[0]Initialize the result with the first element of the array.
Starting res with nums[0] ensures the algorithm correctly handles arrays with a single element and sets a valid baseline for comparison.
res = max(res, cur_max)Update the global maximum product with the current maximum product.
This ensures the algorithm keeps track of the best product found so far across all subarrays.
if not nums:Check if the input array is empty.
This early check prevents errors and unnecessary computation by handling the edge case where no subarray exists.
cur_min, cur_max = 1, 1Initialize current minimum and maximum products to 1.
Setting cur_min and cur_max to 1 prepares for multiplication without affecting the first iteration, enabling correct tracking of products.
temp_max_product = cur_max * nCalculate the product of the current maximum product and the current number.
Storing this intermediate value allows the algorithm to compare multiple candidates for the new maximum and minimum products without losing the original cur_max value.
return resReturn the maximum product found.
Returning res provides the final answer after processing all elements, completing the algorithm.
return 0Return 0 for empty input.
Returning 0 is the correct response when no elements exist to form a subarray product.
for n in nums:Iterate through each number in the array.
This loop processes every element to update the running maximum and minimum products, which is essential for finding the maximum product subarray.
Test Your Understanding
Why must the algorithm track both the current maximum and minimum products at each step?
Because a negative number can turn the minimum product into a maximum product and vice versa, tracking both ensures that the algorithm correctly captures the effect of sign changes on the product.
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