# 152. Maximum Product Subarray 乘积最大子数组

@TOC

## # 题目描述

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) {
const int N = nums.size();
int res = INT_MIN;
for (int i = 0; i < N; ++i) {
int cur = 1;
for (int j = i; j < N; ++j) {
if (j == i)
cur = nums[i];
else
cur = cur * nums[j];
res = max(res, cur);
}
}
return res;
}
};
``````

### # 动态规划

• 当前的最大值等于已知的最大值、最小值和当前值的乘积，当前值，这三个数的最大值。
• 当前的最小值等于已知的最大值、最小值和当前值的乘积，当前值，这三个数的最小值。
• 结果是最大值数组中的最大值。

``````class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
N = len(nums)
f = [0] * N
g = [0] * N
f[0] = g[0] = res = nums[0]
for i in range(1, N):
f[i] = max(f[i - 1] * nums[i], nums[i], g[i - 1] * nums[i])
g[i] = min(f[i - 1] * nums[i], nums[i], g[i - 1] * nums[i])
res = max(res, f[i])
return res
``````

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

``````class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
N = len(nums)
f = g = res = nums[0]
for i in range(1, N):
pre_f, pre_g = f, g
f = max(pre_f * nums[i], nums[i], pre_g * nums[i])
g = min(pre_f * nums[i], nums[i], pre_g * nums[i])
res = max(res, f)
return res
``````

``````class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
N = len(nums)
f = g = res = nums[0]
for i in range(1, N):
if nums[i] > 0:
f, g = max(f * nums[i], nums[i]), min(g * nums[i], nums[i])
else:
f, g = max(g * nums[i], nums[i]), min(f * nums[i], nums[i])
res = max(res, f)
return res
``````

``````class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
N = len(nums)
f = g = res = nums[0]
for i in range(1, N):
if nums[i] < 0:
f, g = g, f
f, g = max(f * nums[i], nums[i]), min(g * nums[i], nums[i])
res = max(res, f)
return res
``````

## # 参考资料

http://www.cnblogs.com/grandyang/p/4028713.html

## # 日期

2018 年 10 月 20 日 —— 10月剩余的时间又不多了