1 Maximum Product Subarray_Leetcode

时间:2022-04-25 11:24:54

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