# An implementation of the suggested solution (dynamic programming)

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

• thanks for sharing, but the suggested solution also mentioned that an array keeping track of the the local min&max is not necessary, instead, for each step we only need to know the pre-max&min, so two variables are sufficient

• Yeah I think you are right. Thank you so much for advice.

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

};

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