Watch 10 video solutions for Maximum Product Subarray, a medium level problem involving Array, Dynamic Programming. This walkthrough by NeetCode has 541,092 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums, find a subarray 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.
Example 1:
Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums is guaranteed to fit in a 32-bit integer.Problem Overview: Given an integer array, find the contiguous subarray that has the largest product and return that product. Negative numbers make this problem tricky because multiplying two negatives can suddenly produce a large positive value.
Approach 1: Dynamic Programming with Two Variables (O(n) time, O(1) space)
This approach tracks two values while scanning the array: the maximum product ending at the current index and the minimum product ending at the current index. The minimum is necessary because a negative number can flip a small negative product into a large positive one. For every element num, compute three candidates: num, num * currentMax, and num * currentMin. Update the running maximum and minimum accordingly. Maintain a global result that stores the best product seen so far.
The key insight is that the optimal subarray ending at position i depends only on the previous step. This makes the algorithm a compact form of dynamic programming with constant memory. You iterate once through the array, updating two variables and the result. Time complexity is O(n) and space complexity is O(1), making it the standard optimal solution used in interviews.
Approach 2: Prefix and Suffix Product Tracking (O(n) time, O(1) space)
This method scans the array twice conceptually by tracking cumulative products from both directions. Compute a running prefix product from left to right and a suffix product from right to left. If a zero appears, reset the running product because any subarray crossing that zero becomes zero. The maximum product subarray must appear either in a prefix segment or a suffix segment when negatives are balanced.
During the traversal, update the result with the maximum of the prefix product, suffix product, and current best. This technique works because reversing the traversal effectively handles cases where an odd number of negative values causes the optimal product to appear after dropping the first negative element. The algorithm still runs in O(n) time with O(1) space and uses simple multiplication without maintaining two states.
Recommended for interviews: The dynamic programming approach with two variables is the solution most interviewers expect. It shows you understand how negative numbers affect products and how to maintain both maximum and minimum states. The prefix–suffix approach is also efficient but less commonly discussed during interviews. Demonstrating the brute reasoning about negatives first and then implementing the DP solution signals strong understanding of dynamic programming patterns on arrays.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Two Variables | O(n) | O(1) | Best general solution; handles negative numbers efficiently and is the most common interview answer. |
| Prefix and Suffix Product Tracking | O(n) | O(1) | Useful alternative when reasoning about products from both directions or handling segments separated by zeros. |