# [LeetCode] 152. Maximum Product Subarray 求最大子数组乘积

2021年09月15日 阅读数：1

Given an integer array `nums`, find the contiguous subarray within an array (containing at least one number) which has the largest product.html

Example 1:java

```Input: [2,3,-2,4]
Output: `6`
Explanation: [2,3] has the largest product 6.
```

Example 2:python

```Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.```

53. Maximum Subarray 的变形，求和的时候，遇到0不会改变最大值，遇到负数也只是会减少最大值。而在求最大子数组乘积，遇到0会使整个乘积为0，遇到负数会使最大乘积变成最小乘积。数组

Java:url

```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;
}
```

Python:code

```class Solution:
# @param A, a list of integers
# @return an integer
def maxProduct(self, A):
global_max, local_max, local_min = float("-inf"), 1, 1
for x in A:
local_max, local_min = max(x, local_max * x, local_min * x), min(x, local_max * x, local_min * x)
global_max = max(global_max, local_max)
return global_max
```

Python:htm

```class Solution2:
# @param A, a list of integers
# @return an integer
def maxProduct(self, A):
global_max, local_max, local_min = float("-inf"), 1, 1
for x in A:
local_max = max(1, local_max)
if x > 0:
local_max, local_min = local_max * x, local_min * x
else:
local_max, local_min = local_min * x, local_max * x
global_max = max(global_max, local_max)
return global_max　　```

Python: woblog

```class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp1 = [0] * len(nums)
dp1[0] = nums[0]
dp2 = [0] * len(nums)
dp2[0] = nums[0]
res = dp1[0]
for i in xrange(1, len(nums)):
dp1[i] = max(dp1[i-1] * nums[i], dp2[i-1] * nums[i], nums[i])
dp2[i] = min(dp1[i-1] * nums[i], dp2[i-1] * nums[i], nums[i])
res = max(res, dp1[i])

return res
```

C++:get

```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;
}
};
```

C++:

```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;
}
};
```

C++:

```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;
}
};
```

C++:

```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;
}
};
```

[LeetCode] 53. Maximum Subarray 最大子数组