Leetcode---Maximum Product Subarray

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.

求一串数字的最大子串积。这不禁让人想到了最大子串和的那个问题，不过这个问题和那个不一样，子串和是这么做的：

从头到尾尝试着累加子串字符和为sum，一旦sum<0，则sum=0，然后继续累加，在这个过程中一直更新最大值。

我开始做这道题用的是DP，本质上就是遍历，但因为是DP，报了Memory Limit Exceeded错误。

int maxProduct(int A[], int n) {
    vector<vector<int>> dp(n,vector<int>(n,0));
    int max=A[0];
    for(int i=0;i<n;i++){
        dp[i][i]=A[i];
        if(dp[i][i]>max)
            max=dp[i][i];
    }
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            dp[i][j]=dp[i][j-1]*A[j];
            if(dp[i][j]>max)
            max=dp[i][j];
        }
    }
    return max;
}

后来只好放弃了遍历，采用另一种思路：
子串积要是有S[i]参与，则可能是：
1） i之前的最大的子串积*S[i]
2） i之前的最小的子串积*S[i]
3） S[i]
取它们的最大值，即为以S[i]为尾的最大子串积，把i从0到n-1遍历，得到最大子串积。

代码如下，注意这段代码稍作改动可求最小子串积。

int maxProduct(int A[], int n) {
    if(n==0)
        return 0;
    else if(n==1)
        return A[0];
    else{
        int curmax=A[0];
        int curmin=A[0];
        int result=A[0];
        for(int i=1;i<n;i++){
            int a=curmax*A[i];
            int b=curmin*A[i];
            curmax=max(A[i],max(a,b));
            curmin=min(A[i],min(a,b));
            result=max(result,curmax);
        }
        return result;
    }
}