My solution in JAVA, O(n)


  • 1
    T

    it's quite clumsy, but probably the idea is different from other people

    basically because we don't have numbers between 0 and 1, so the absolute value of product always goes up as you add more numbers, unless u reach 0 or negative numbers. but if u have 2 negative numbers, you win again. and if u reach a zero, u can't include it anymore, and since we want continuous, all previous numbers are useless. so we can divide the entire array into SECTIONS by "0".
    i.e.

    something like
    p p p p n p p p n pp 0 ppppp

    here "n" means negative number, and "p" means positive. in the code, in the inner while loop, I look at one section cut off by 0, and this section is divided into sections by "n", once I get 2 negative numbers, I roll them up into "section" again, and compare against the remaining.

    in cases like "-1 -2 -3", I may get -1 * -2 = 2, = section1, and -3 , and get max 2

    to guard against such cases, I compute again from right to left, and get -1 , (-2 * -3) , which 6

    public class Solution {
        public int maxProduct(int[] A) {
            if (A.length == 0) return 0;
            int best = maxProduct2(A);
            int l = 0;int h = A.length-1;
            while(l<h) {
                int tmp = A[l];
                A[l] = A[h];
                A[h] = tmp;
                l++;h--;
            }
            best = Math.max(best, maxProduct2(A));
            return best;
        }
    public int maxProduct2(int[] A) {
        int i=0;
        int best = Integer.MIN_VALUE;
        while(i<A.length) {
            int section =1 ;
            int sectionLen = 0;
            int section1=1 ;
            int section1Len = 0;
            int sectionCnt = 0; // how many CLOSED sections we have seen
            int lastNeg = 1;
            while(i<A.length && A[i]!=0) {
                if (A[i] > 0) {
                    section *= A[i];
                    sectionLen ++;
                } else { // <0
                    if (sectionCnt == 0) {
                        sectionCnt = 1;
                        section1 = section;
                        section1Len = sectionLen;
                        section = 1;
                        sectionLen = 0;
                        lastNeg = A[i];
                    } else {
                        section *= -A[i] * section1 * (-lastNeg);
                        sectionCnt = 0;
                        sectionLen = 2;
                    }
                }
                i++;
            }
            
            if (sectionCnt == 1 )
                if (section1Len > 0) {
                best = Math.max(best, section1);
            } else {
                best = Math.max(best, lastNeg);
            }
            if (sectionLen > 0 )
            best = Math.max(best, section);
            if (i < A.length) {
                // A[i] must be 0
                best = Math.max(best, 0);
                i++;
            }
                 
        }
        
        return best;
    }
    

    }


Log in to reply
 

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