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.
This approach maintains two variables for each element in the array: the maximum product up to that element and the minimum product up to that element. We update these variables as we iterate through the array. This accommodates both the product of consecutive elements and the inversion effect caused by negative numbers.
The C solution initializes variables for the maximum and minimum products at the starting element of the array. We then iterate through the array, swapping the current max and min products when encountering a negative number, thereby adjusting the maximum product accordingly.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as we are using only a constant amount of extra space.
In this approach, we calculate the prefix product and suffix product for each element of the array, capturing the highest product subarray that may begin or end with an array boundary. We track the maximum of the prefix or suffix products.
The C implementation iterates over the nums array, simultaneously updating prefix and suffix products. These products are reset to nums[i] or nums[numsSize-1-i] respectively if their accumulated product becomes zero.
Time Complexity: O(n)
Space Complexity: O(1)
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Dynamic Programming with Two Variables | Time Complexity: O(n), where n is the number of elements in the array. |
| Prefix and Suffix Product Tracking | Time Complexity: O(n) |
| Default Approach | — |
| 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. |
Maximum Product Subarray - Dynamic Programming - Leetcode 152 • NeetCode • 541,092 views views
Watch 9 more video solutions →Practice Maximum Product Subarray with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor