Maximum Product Subarray - Solution & Explanation
Problem Statement
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] <= 10- The product of any subarray of
numsis guaranteed to fit in a 32-bit integer.
Approach Overview
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 1: Dynamic Programming with Two Variables
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.
Complexity
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.
Approach 2: Prefix and Suffix Product Tracking
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.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Maximum Product Subarray - Dynamic Programming - Leetcode 152 • NeetCode • 561,465 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Product Subarray easy or hard?
How to solve Maximum Product Subarray in O(n)?
What is the best approach for Maximum Product Subarray?
What data structure is used in Maximum Product Subarray?
What is the time complexity of Maximum Product Subarray?
Maximum Product Subarray Python or Java solution approach?
Is Maximum Product Subarray asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Maximum Product Subarray with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor