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.The #152 Maximum Product Subarray problem asks you to find the contiguous subarray within an array that has the largest product. Unlike sum-based problems, products behave differently because multiplying by a negative number can flip the sign of the result. This means a previously small (negative) value could suddenly become the maximum when multiplied by another negative number.
A common strategy uses dynamic programming. While iterating through the array, maintain two running values: the maximum product ending at the current index and the minimum product ending at the current index. Tracking both is important because the minimum value might turn into the maximum after multiplication by a negative number.
At each step, update these values based on the current element and the previous products, while keeping track of the global maximum. This approach processes the array in a single pass, resulting in O(n) time complexity and O(1) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (tracking max and min products) | O(n) | O(1) |
NeetCode
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.
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.
1#include <stdio.h>
2
3int maxProduct(int* nums, int numsSize) {
4 int maxProduct = nums[0];
5
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.
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.
Time Complexity: O(n)
Space Complexity: O(1)
1#include <vector>
2#include <iostream>
int maxProduct(std::vector<int>& nums) {
int maxProduct = nums[0];
int prefixProduct = 1;
int suffixProduct = 1;
for (int i = 0; i < nums.size(); i++) {
prefixProduct = prefixProduct == 0 ? nums[i] : prefixProduct * nums[i];
suffixProduct = suffixProduct == 0 ? nums[nums.size() - 1 - i] : suffixProduct * nums[nums.size() - 1 - i];
maxProduct = std::max(maxProduct, std::max(prefixProduct, suffixProduct));
}
return maxProduct;
}
int main() {
std::vector<int> nums = {2, 3, -2, 4};
std::cout << maxProduct(nums) << std::endl;
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Maximum Product Subarray is a common medium-level interview question and has appeared in interviews at major tech companies. It tests understanding of dynamic programming, edge cases with negative numbers, and efficient array traversal.
The optimal approach uses dynamic programming by tracking both the maximum and minimum product ending at each index. This is necessary because negative numbers can flip the sign of the product. The algorithm runs in O(n) time and uses constant extra space.
No special data structure is required for the optimal solution. The problem can be solved using a few variables to track the current maximum and minimum products, making it a space-efficient dynamic programming approach.
Because multiplying by a negative number can turn a large negative product into a large positive one. By keeping both the maximum and minimum products at each step, the algorithm correctly handles sign changes and finds the optimal subarray.
The C++ code uses the prefix and suffix method along with a straightforward method of tracking maximum product while iterating the nums vector from start and end synchronously.