Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Companies:
LinkedIn, Google, Amazon, Microsoft, Adobe
Related Topics:
Array, Dynamic Programming
Similar Questions:
- Maximum Subarray (Easy)
- House Robber (Easy)
- Product of Array Except Self (Medium)
- Maximum Product of Three Numbers (Easy)
- Subarray Product Less Than K (Medium)
The problem is the same as finding the longest subarray with even number negative numbers without 0.
We can use two pointers.
- the fast pointer keeps reading number until it reaches 0 or end of array; meanwhile, we keep updating answer with the greatest product we've seen.
- if the product is negative, we move the slow pointer until the product becomes positive, and update the answer if it's greater.
- we move both pointers to the next non-zero number and loop until the fast pointer reaches the end.
// OJ: https://leetcode.com/problems/maximum-product-subarray/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int maxProduct(vector<int>& A) {
int ans = A[0], N = A.size(), j = 0;
while (j < N) {
int i = j, prod = 1;
while (j < N && A[j] != 0) {
prod *= A[j++];
ans = max(ans, prod);
}
if (j < N) ans = max(ans, 0);
while (i < N && prod < 0) {
prod /= A[i++];
if (i != j) ans = max(ans, prod);
}
while (j < N && A[j] == 0) ++j;
}
return ans;
}
};Let max[i] be the maximum product of subarrays ending at A[i], min[i] be the minimum product of subarrays ending at A[i].
max[i] = max(A[i], A[i] * max[i - 1], A[i] * min[i - 1])
min[i] = min(A[i], A[i] * max[i - 1], A[i] * min[i - 1])
// OJ: https://leetcode.com/problems/maximum-product-subarray/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int maxProduct(vector<int>& A) {
int maxProd = 1, minProd = 1, ans = INT_MIN;
for (int n : A) {
int a = n * maxProd, b = n * minProd;
maxProd = max({n, a, b});
minProd = min({n, a, b});
ans = max(ans, maxProd);
}
return ans;
}
};Similar problem: 1567. Maximum Length of Subarray With Positive Product (Medium)