Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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};