Found a amazing logic by @haoel


  • 0
    S
        int maxPrev = A[0], minPrev = A[0];
        int maxHere = A[0];
        int maxProd = A[0];
    
    for (int i=1; i<A.size(); i++){
        
        maxHere = max( max( maxPrev * A[i], minPrev * A[i] ), A[i] );
        maxProd = max(maxHere, maxProd);
        
        
        minPrev = min( min( maxPrev * A[i], minPrev * A[i] ), A[i] );
        maxPrev = maxHere;
    }
    return maxProd;
    

    I‘m confused.

    .


  • 0
    H

    Here we keep track of the largest product as well as the smallest product. It's clear that the smallest product could become the largest when multiplied by a negative number.
    We denote largest product subarray as L(k) and smallest as S(k), then:

    L(k) = max(A(k), A(k)*L(k-1), A(k)*S(k-1))
    S(k) = min(A(k), A(k)*L(k-1), A(k)*S(k-1))
    

    The maximum in L(k) is then the desired answer.


  • 0
    S

    thanks so much for your answer.

    I need to think it over


Log in to reply
 

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