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 {
7
8public:
9
10 //dp
11 //dp[i]表示当前的最大乘积。
12 //用了滚动数组优化空间/
13 int maxProduct(vector<int>& nums) {
14 int siz = nums.size();
15 int mnpre,mncur,mxpre,mxcur;
16 int ret;
17 ret = mnpre = mncur = mxpre = mxcur = nums[0];
18 for ( int i = 1 ; i < siz ; i++ )
19 {
20 mncur = min(nums[i],min(nums[i]*mnpre,nums[i]*mxpre));
21 mxcur = max(nums[i],max(nums[i]*mnpre,nums[i]*mxpre));
22 ret = max(ret,mxcur);
23 mnpre = mncur;
24 mxpre = mxcur;
25 }
26 return ret;
27
28 }
29
30};