找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
例如， 给定序列 [2,3,-2,4]，
其中乘积最大的子序列为 [2,3] 其乘积为 6。
详见：https://leetcode.com/problems/maximum-product-subarray/description/
方法一：
class Solution {
public:
int maxProduct(vector<int>& nums) {
int size=nums.size();
if(size==0||nums.empty())
{
return 0;
}
vector<int> f(size,0),g(size,0);
int res=nums[0];
f[0]=nums[0];
g[0]=nums[0];
for(int i=1;i<size;++i)
{
f[i]=max(nums[i],max(nums[i]*f[i-1],nums[i]*g[i-1]));
g[i]=min(nums[i],min(nums[i]*g[i-1],nums[i]*f[i-1]));
res=max(res,f[i]);
}
return res;
}
};
方法二：优化空间复杂度
class Solution {
public:
int maxProduct(vector<int>& nums) {
int size=nums.size();
if(size==0||nums.empty())
{
return 0;
}
int mx=nums[0];
int mn=nums[0];
int res=nums[0];
for(int i=1;i<size;++i)
{
int tmax=mx,tmin=mn;
mx=max(nums[i],max(tmax*nums[i],tmin*nums[i]));
mn=min(nums[i],min(tmax*nums[i],tmin*nums[i]));
res=max(res,mx);
}
return res;
}
};
参考：https://www.cnblogs.com/grandyang/p/4028713.html