Coding Interview PatternsMaximum Product Subarray
MediumDynamic Programming
Maximum Product Subarray
Explanation & Solution
Description
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Input:nums = [2,3,-2,4]
0
2
1
3
2
-2
3
4
Output: 6
Explanation: The subarray [2,3] has the largest product 6.
Constraints
1 <= nums.length <= 2 * 10^4-10 <= nums[i] <= 10- The product of any subarray of
numsis guaranteed to fit in a 32-bit integer.
Approach
Dynamic Programming pattern
1. Initialize Variables
- Set
result = nums[0]to track the global maximum product. - Set
curMax = nums[0]to track the maximum product ending at the current position. - Set
curMin = nums[0]to track the minimum product ending at the current position (important because a negative minimum can become the maximum when multiplied by a negative number).
2. Iterate Through the Array
- For each element
nums[i]starting from index 1: - Compute three candidates:
nums[i]alone (starting a new subarray),nums[i] * curMax(extending the max subarray), andnums[i] * curMin(extending the min subarray). - Update
curMaxto the maximum of the three candidates. - Update
curMinto the minimum of the three candidates.
3. Track the Global Maximum
- After updating
curMaxat each step, compare it withresultand keep the larger value.
4. Return the Result
- After processing all elements, return
resultas the maximum product of any contiguous subarray.
Key Insight
- The key challenge with products is that negative numbers can flip the sign. A very negative product can become the largest positive product when multiplied by another negative number. By tracking both the running maximum and minimum products, we correctly handle sign changes and zeros.
Time
O(n)a single pass through the array.Space
O(1)only a few tracking variables are used.Visualization
Input:
[2, 3, -2, 4]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps