A quite direct but clumsy O(n) solution in C. Just have a look...


  • 0
    Y

    #ATTENTION:

    THIS IS A STUPID SOLUTION, SIMPLE BUT NOT CONCISE, CLUMSY BUT QUITE DIRECT

    A quick description:

    0 - Absolutely, more numbers means bigger absolute value. The trap is : zero & negative numbers

    Key point is splitting the array into 3 parts( by negative numbers):

    head(no negative numbers), middle, tail(same as head); The format is:[head, negnum1, middle, negnum2, tail]

    e.g.1[1, 2, 3, -1, 4, 5, 6, -2, 7, 8] ——> [1*2*3, -1, 4*5*6, -2, 7*8] ——> [6,-1,120,-2,56] ——>

    because middle is positive, so we can add both tail and head into product: 6*-1*120*-2*56

    e.g.2 [1,2,-1,-4,-5,-6,-2,7,8] ——> [2,-1,-120,-2,56]——>

    because middle is negative &&|2*-1|<|-2*56|, so choose: [-120, -2, 56] ——> -120*-2*56 as result.

    e.g.3 [A,0,B]——> deal with [A], then deal with [B]——>

    return max(A.max_product, B.max_product)

    ##STEPS

    1 - filter zeros use maxProduct(), for example: split the array [A,0,B,0,C] into [A], [B], [C]

    2 - deal with sub-problem [A], [B], [C]in max_no_zeor()

    3 - in max_no_zero() we do:

    1- scan from head, find a negative number A[negindex_front] [e.g. number = -1]

    2 - scan from tail, find a negative number A[negindex_back] [e.g. number = -2]

    3 - calculate the product between negindex_front and negindex_back

    now we get somethin like this: [product_head, -1, product_middle, -2, product_tail]

    only 5 numbers... you know what to do....

    ##Oh... after unlocking the answer, I realized how stupid it is!
    ##Anyway, not very hard to understand
    this is the code:

    int max(int a,int b){return a>b?a:b;}
    int max_no_zero(int *A,int start, int end){
        /*void arr*/
        if(end==start)
            return INT_MIN;
        /*only one element*/
        if(end==start+1)
            return A[start];
        /*calcu from front*/
        int front_pro = 1, negindex_front;
        for(negindex_front=start;negindex_front<end;negindex_front++){
            if(A[negindex_front]<0)
                break;
            front_pro *= A[negindex_front];
        }
        /*if no negative number*/
        if(negindex_front==end)
            return front_pro;
        /*calcu from back*/
        int back_pro = 1,negindex_back;
        for(negindex_back=end-1;negindex_back>start-1;negindex_back--){
            if(A[negindex_back]<0)
                break;
            back_pro *= A[negindex_back];
        }
        /*if only one negative number*/
        if(negindex_front==negindex_back)
            return max(front_pro,back_pro);
        /*calcu middle*/
        int middle_pro = 1;
        for(int i=negindex_front+1;i<negindex_back;i++)
            middle_pro *= A[i];
        if(middle_pro>0)
            return front_pro*A[negindex_front]*middle_pro*A[negindex_back]*back_pro;
        else if(middle_pro==0)
            return 0;
        else{
            int multi = max(front_pro*A[negindex_front]*-1,back_pro*A[negindex_back]*-1);
            return multi*middle_pro*-1;
        }
    }
    
    int maxProduct(int A[], int n) {
        int start = 0,end; 
        int max_pro = A[0];
        int zero_exist = false;
        while(start<n){
            for(end=start;end<n;end++){
                if(A[end]==0){
                    zero_exist = true;
                    break;
                }
            }
            max_pro = max(max_pro,max_no_zero(A,start,end));
            start = end+1;
        }
        if(max_pro<0&&zero_exist)
            return 0;
        else
            return max_pro;
    }

Log in to reply
 

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