leetcode 152. Maximum Product Subarray (最大连续子序列乘积，dp)
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
思路：由于有正，有负，还有0.。。所以比最大子串之和要复杂一些。。。
dp[i].max表示到当前位置的最大乘积。
dp[i].min表示到当前位置的最小乘积。
dp[i].max = max{dp[i-1].maxa[i],dp[i-1].mina[i],a[i]};
dp[i].min同理
边界dp[i].max = dp[i].min = a[0]
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月14日 星期五 18时57分13秒
4File Name :152.cpp
5************************************************ */
6class Solution {
public:
1 //dp
2 //dp[i]表示当前的最大乘积。
3 //用了滚动数组优化空间/
4 int maxProduct(vector<int>& nums) {
5 int siz = nums.size();
6 int mnpre,mncur,mxpre,mxcur;
7 int ret;
8 ret = mnpre = mncur = mxpre = mxcur = nums[0];
9 for ( int i = 1 ; i < siz ; i++ )
10 {
11 mncur = min(nums[i],min(nums[i]*mnpre,nums[i]*mxpre));
12 mxcur = max(nums[i],max(nums[i]*mnpre,nums[i]*mxpre));
13 ret = max(ret,mxcur);
14 mnpre = mncur;
15 mxpre = mxcur;
16 }
17 return ret;
}
};