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 value. Negative numbers and zeros make this problem tricky because multiplying two negatives can flip the sign and produce a larger product.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
The most direct way is to generate every possible subarray and compute its product. Use two nested loops: the outer loop selects the starting index and the inner loop multiplies elements while extending the subarray to the right. Track the maximum product seen so far. This approach is useful for understanding the problem constraints and verifying edge cases like zeros and negative numbers. However, the O(n²) time complexity becomes too slow for large arrays.
Approach 2: Dynamic Programming with Two Variables (O(n) time, O(1) space)
The optimal insight is that you must track both the maximum and minimum product ending at each position. A negative number can turn the smallest product into the largest when multiplied. During iteration, maintain two values: maxProd and minProd. For each element, compute the new maximum and minimum among three candidates: the current number, num * maxProd, and num * minProd. Update the global answer with the current maxProd. This technique is a classic application of dynamic programming on an array, compressing the state to constant space.
Approach 3: Prefix and Suffix Product Tracking (O(n) time, O(1) space)
Another clean approach scans the array from both directions. Maintain a running product from the left (prefix) and from the right (suffix). Whenever a zero appears, reset the product to 1 since any product including zero collapses. At each step, update the result with the maximum of the prefix and suffix products. This works because the maximum product subarray must appear either after the first negative or before the last negative in a segment without zeros. The method avoids explicit min/max tracking while still handling sign flips.
Recommended for interviews: Interviewers typically expect the dynamic programming approach with two variables. It demonstrates that you understand how negative numbers affect products and how to maintain both maximum and minimum states efficiently. Mentioning the brute force method first shows baseline reasoning, but implementing the O(n) DP solution signals strong problem‑solving skills.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| 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) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n²) | O(1) | Good for understanding the problem or validating small test cases |
| Dynamic Programming with Max/Min Tracking | O(n) | O(1) | Best general solution and the approach most interviewers expect |
| Prefix and Suffix Product Scan | O(n) | O(1) | Useful alternative when reasoning about segments separated by zeros |
Maximum Product Subarray - Dynamic Programming - Leetcode 152 • NeetCode • 452,934 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