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


  • 0
    T

    /*

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

Log in to reply
 

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