int maxProduct(int A[], int n) {
if(n == 0){
return 0;
}
int* maxdp = new int[n];
int* mindp = new int[n];
maxdp[0] = A[0];
mindp[0] = A[0];
int maxProduct = A[0];
for(int i = 1; i < n; i++){
if(A[i] > 0){
maxdp[i] = max(maxdp[i  1] * A[i], A[i]);
mindp[i] = min(mindp[i  1] * A[i], A[i]);
}
else{
maxdp[i] = max(mindp[i  1] * A[i], A[i]);
mindp[i] = min(maxdp[i  1] * A[i], A[i]);
}
maxProduct = max(maxProduct, maxdp[i]);
}
return maxProduct;
}
An implementation of the suggested solution (dynamic programming)


class Solution {
public:
int maxProduct(int A[], int n) {
if (n <1 ) return 0;// assume no overflow, underflow int maxPro = A[0]; int minPro = A[0]; int res = A[0]; for (int i = 1; i < n; i++){ if(A[i] > 0) { maxPro = max(maxPro * A[i], A[i]); minPro = min(minPro * A[i], A[i]); } else { // covers A[i] = 0 int temp = maxPro; // !!! record the maxPro maxPro = max(minPro * A[i], A[i]); minPro = min(temp * A[i], A[i]); } if (maxPro > res) res = maxPro; } return res; }
};