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.

Since two negative numbers may multiply and get a large number, I need to track the minimum number of each position in the sequence.

At each point, the maximum can be obtained by three numbers:

1. A[i]

2. A[i] * curmax

3. A[i] * curmin

Similar as the minimum update.

FIRST TRY ERROR:

I should use temp variable to store the curmax, since the update of curmin use the previous value of curmax.

Code:

class Solution {public:    int maxProduct(int A[], int n) {        if(n == 0 || A == NULL) return 0;        int curmax = A[0], curmin = A[0];        int res = A[0];                for(int i = 1; i < n; i++)        {            int tmpmax = curmax, tmpmin = curmin;   // take care, curmax is used when calc curmin, so do not update            curmax = max(max(A[i], A[i]*tmpmax), A[i]*tmpmin);            curmin = min(min(A[i], A[i]*tmpmax), A[i]*tmpmin);            if(curmax > res) res = curmax;        }        return res;    }};

1 Maximum Product Subarray_Leetcode