# My simple C++ (not DP) accepted solution, any thought to make it more efficient?

• class Solution {
public:
int maxProduct(int A[], int n) {

``````int* max = new int[n];
int* min = new int[n];

min[0]=A[0];
max[0]=A[0];
int i;
for ( i=1; i<n;i++){

if (A[i]>0){
max[i]= (A[i]*max[i-1]>A[i])? A[i]*max[i-1] : A[i];
min[i]= (A[i]*min[i-1]<A[i])? A[i]*min[i-1] : A[i];
}
else{
max[i]= (A[i]*min[i-1]>A[i])? A[i]*min[i-1] : A[i];
min[i]= (A[i]*max[i-1]<A[i])? A[i]*max[i-1] : A[i];
}

}
int ans=max[0];
for (int j=0;j<i;j++)
{
if (max[j]>ans) {ans=max[j];}
}

return (ans);
``````

}
};

• Of course, the code can be more efficient.

When calculating `max[i]`, we just use `max[i - 1]` and `min[i - 1]`, and the same to `min[i]`. So the `max` and `min` array is redundant.

It should be noticed that when 'A[i] < 0', we should keep the previous `max[i - 1]` first.

Here is a more concise code based on your idea.

``````class Solution {
public:
int maxProduct(int A[], int n) {
int ret, maxP, minP;
ret = maxP = minP = A[0];
for (int idx = 1; idx < n; ++idx) {
if (A[idx] > 0) {
maxP = max(maxP * A[idx], A[idx]);
minP = min(minP * A[idx], A[idx]);
}
else {
int temp = maxP;
maxP = max(minP * A[idx], A[idx]);
minP = min(temp * A[idx], A[idx]);
}
if (maxP > ret) {
ret = maxP;
}
}
return ret;
}
};``````

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