# 152. Maximum Product Subarray

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.
``````

``````class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0], n = nums.size();
vector<int> f(n, 0), g(n, 0);
f[0] = nums[0];
g[0] = nums[0];
for (int i = 1; i < n; ++i) {
f[i] = max(max(f[i - 1] * nums[i], g[i - 1] * nums[i]), nums[i]);
g[i] = min(min(f[i - 1] * nums[i], g[i - 1] * nums[i]), nums[i]);
res = max(res, f[i]);
}
return res;
}
};
``````

Besides keeping track of the largest product, we also need to keep track of the smallest product. Why? The smallest product, which is the largest in the negative sense could become the maximum when being multiplied by a negative number.

Let us denote that:

``````f(k) = Largest product subarray, from index 0 up to k.
``````

Similarly,

``````g(k) = Smallest product subarray, from index 0 up to k.
``````

Then,

``````f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] )
g(k) = min( g(k-1) * A[k], A[k], f(k-1) * A[k] )
``````

There we have a dynamic programming formula. Using two arrays of size  n , we could deduce the final answer as f( n -1). Since we only need to access its previous elements at each step, two variables are sufficient.

``````public int maxProduct(int[] A) {
assert A.length > 0;
int max = A[0], min = A[0], maxAns = A[0];
for (int i = 1; i < A.length; i++) {
int mx = max, mn = min;
max = Math.max(Math.max(A[i], mx * A[i]), mn * A[i]);
min = Math.min(Math.min(A[i], mx * A[i]), mn * A[i]);
maxAns = Math.max(max, maxAns);
}
return maxAns;
}
``````

``````class Solution {
public:
int maxProduct(vector<int>& nums) {
if (nums.empty()) return 0;
int res = nums[0], mn = nums[0], mx = nums[0];
for (int i = 1; i < nums.size(); ++i) {
int tmax = mx, tmin = mn;
mx = max(max(nums[i], tmax * nums[i]), tmin * nums[i]);
mn = min(min(nums[i], tmax * nums[i]), tmin * nums[i]);
res = max(res, mx);
}
return res;
}
};
``````

1. 当遍历到一个正数时，此时的最大值等于之前的最大值乘以这个正数和当前正数中的较大值，此时的最小值等于之前的最小值乘以这个正数和当前正数中的较小值。

2. 当遍历到一个负数时，先用一个变量t保存之前的最大值 mx，然后此时的最大值等于之前最小值乘以这个负数和当前负数中的较大值，此时的最小值等于之前保存的最大值t乘以这个负数和当前负数中的较小值。

3. 在每遍历完一个数时，都要更新最终的最大值。

P.S. 如果这里改成求最小值的话，就是求最小子数组乘积，并且时间复杂度是醉人的 O(n)，是不是很强大呢，参见代码如下：

``````class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0], mx = res, mn = res;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] > 0) {
mx = max(mx * nums[i], nums[i]);
mn = min(mn * nums[i], nums[i]);
} else {
int t = mx;
mx = max(mn * nums[i], nums[i]);
mn = min(t * nums[i], nums[i]);
}
res = max(res, mx);
}
return res;
}
};
``````

``````class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0], mx = res, mn = res;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] < 0) swap(mx, mn);
mx = max(nums[i], mx * nums[i]);
mn = min(nums[i], mn * nums[i]);
res = max(res, mx);
}
return res;
}
};
``````

``````class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0], prod = 1, n = nums.size();
for (int i = 0; i < n; ++i) {
res = max(res, prod *= nums[i]);
if (nums[i] == 0) prod = 1;
}
prod = 1;
for (int i = n - 1; i >= 0; --i) {
res = max(res, prod *= nums[i]);
if (nums[i] == 0) prod = 1;
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/152

Maximum Subarray

House Robber

Product of Array Except Self

Maximum Product of Three Numbers

Subarray Product Less Than K

https://leetcode.com/problems/maximum-product-subarray/

https://leetcode.com/problems/maximum-product-subarray/discuss/48302/2-passes-scan-beats-99

https://leetcode.com/problems/maximum-product-subarray/discuss/48261/share-my-dp-code-that-got-ac

https://leetcode.com/problems/maximum-product-subarray/discuss/48252/sharing-my-solution-o1-space-on-running-time

https://leetcode.com/problems/maximum-product-subarray/discuss/48230/possibly-simplest-solution-with-on-time-complexity

https://leetcode.com/problems/maximum-product-subarray/discuss/48389/my-concise-dp-on-java-solution-with-o1-extra-space

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation