To share my solution which has overflow considered for Maximum Product Subarray

• /*

I would like to share my solution which has the overflow considered, time O(n) and space O(1)

*/

``````int maxProduct(int A[], int n){
if(n<1)
return 0;

int max = A[0];
int min = A[0];
int maxAns = A[0];
for(int i = 1; i<n; i++){
if(A[i] == 0) {
max = 0;  //we set both max and min to be 0 whenever current element is 0.
min = 0;
} else {
int max0 = max;
max = max3(A[i], production(A[i],max), production(A[i],min));
min = min3(A[i], production(A[i],min), production(A[i],max0));
}
maxAns = max2(maxAns, max);
}
return maxAns;
}
``````

//min2(), max2(), min3(), max3() and production() are all helper functions.
int min2(int a, int b) {
return a<b? a:b;
}

``````int max2(int a, int b) {
return a>b ? a:b;
}
int max3(int a, int b, int c){
return max2(max2(a,b), c);
}
int min3(int a, int b, int c){
return min2(min2(a,b), c);
}

int production(int a, int b){
//order them so the first argument is always smaller than the second
if(a > b)
return production(b, a);

if(a == 0 || b == 0)
return 0;
if(a > 0 && b > 0) {
if (a > INT_MAX / b)
return INT_MAX;
else
return a*b;
}
if(a < 0 && b < 0) {
if ((b != -1) && (a < INT_MAX / b))
return INT_MAX;
else
return a*b;
}
// neg * pos = neg
// a   * b <> INT_MIN
if( a < INT_MIN / b)
return INT_MIN;
else
return a*b;

}``````

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