class Solution {
public:
int maxProduct(int A[]A, int n) {
// the return value, always equals
// to the maximum product of contiguous
// subarray of A[0:i]
int ret = A[0];
// lastmax = max{ A[j]*A[j+1]*...*A[i] }, j=0:i
// lastmin = min{ A[j]*A[j+1]*...*A[i] }, j=0:i
int lastmax = A[0], lastmin = A[0];
// tmp variable to determine whether a
// new ret value is available after adding A[i]
// and help updating lastmax, lastmin
int foo, bar;
for (int i = 1; i < n; i++) {
// new lastmax/lastmin can only obtained by
// the element A[i] times old lastmax/lastmin
// or the A[i] itself alone.
foo = A[i]*lastmax;
bar = A[i]*lastmin;
if (foo > bar) {
lastmax = max(foo, A[i]);
lastmin = min(bar, A[i]);
} else {
lastmax = max(bar,A[i]);
lastmin = min(foo,A[i]);
}
if (lastmax > ret) ret = lastmax;
}
return ret;
}
};
C++ solution with explanation


My Progarm is Time Limit Exceeded!
And I can't figure it out!
I want somebody who does well in Progarm can help me!class Solution { public: int maxProduct(int A[], int n) { if(A == NULL) { printf("error"); return 1;} if(n == 1) return A[n1]; if(n == 2) return A[n1]*A[n2]; return A[n1][n2]>maxProduct(A,n1)? A[n1][n2]:maxProduct(A,n1); } };