Maximum Product Subarray Problem
Description
LeetCode Problem 152.
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:
1
2
3
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
1
2
3
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 * 10^4
- -10 <= nums[i] <= 10
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int maxProduct(vector<int>& A) {
/* We use dpMax and dpMin arrays where dpMax[i] denotes maximum
subarray product ending at i and dpMin[i] denotes minimum subarray
product ending at i.
At each index i, we will update dpMin[i] as minimum of A[i]
(denotes forming new subarray by choosing current element) and
min(A[i] * dpMin[i-1], A[i] * dpMax[i-1]) (denotes expanding
previous subarray product by including current element).
We do it similarly for dpMax[i] as well. Finally, the maximum
product subarray will be the maximum value in dpMax array. */
vector<int> dpMin(A), dpMax(A);
int ans = A[0];
for(int i = 1; i < size(A); i++) {
dpMin[i] = min(A[i], A[i] * (A[i] >= 0 ? dpMin[i-1] : dpMax[i-1]));
dpMax[i] = max(A[i], A[i] * (A[i] >= 0 ? dpMax[i-1] : dpMin[i-1]));
ans = max(ans, dpMax[i]);
}
return ans;
}
};