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;
}
};