Found a amazing logic by @haoel

  • 0
        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

    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

    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.