# C++ solution with explanation

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

• 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[n-1];
if(n == 2)
return A[n-1]*A[n-2];
return A[n-1][n-2]>maxProduct(A,n-1)? A[n-1][n-2]:maxProduct(A,n-1);

}
};
``````

• use iteration not recursion can pass the test

• Thank you for your sharing. Your code is quite succinct, but I think it is quite hard for new coders to directly come up with this algorithm. Apparently, your algorithm is a dynamic programming, but its format is not so easy to directly come up with.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.