2ms solution above 94%


  • 1
    L

    I used the other folks' solution as a starting point.

    for (int i = 1; i < n; i++) {
        int temp = max;
        max = Math.max(Math.max(max * A[i], min * A[i]), A[i]);
        min = Math.min(Math.min(temp * A[i], min * A[i]), A[i]);
        ret = Math.max(max, ret);
    }
    

    The running time is about 7~8 ms, the reason is that it makes 5 max or min function call and 4 multiplication per A[i], it's kind of expensive. The reason we use library Math.min, Math.max is that there are lots of corner cases, especially the ones that min == 0 and (or) max == 0 (and we really don't want to deal with these annoying cases). So, why not treat these corner cases separately, and for all the other cases, we write the comparing code in-line. The code below runs in 2ms, not whole lot, but somewhat faster than most solutions in the discuss.

    It takes me quite a while to get all the code debugged. But it's totally worth it, not because of achieving a better running time, but: I now have a much clearer understanding of the problem insights, and practiced some code tuning technique.

    public int maxProduct(int[] A) {
        int n = A.length;
        if (n == 0) {
            return 0;
        }
        
        int min = A[0];
        int max = A[0];
        int ret = A[0];
        
        for (int i = 1; i < n; i++) {
            if (min == 0 || max == 0) {
                int temp = max;
                max = Math.max(Math.max(max * A[i], min * A[i]), A[i]);
                min = Math.min(Math.min(temp * A[i], min * A[i]), A[i]);
                ret = Math.max(max, ret);
                continue;
            }
            
            
            if (A[i] > 0) {
                if (min > 0) {
                    min = A[i];
                    max *= A[i];
                } else if (max < 0) {
                    min *= A[i];
                    max = A[i];
                } else {
                    min *= A[i];
                    max *= A[i];
                }
            } else if (A[i] < 0) {
                if (min > 0) {
                    min = max * A[i];
                    max = A[i];
                } else if (max < 0) {
                    max = min * A[i];
                    min = A[i];
                } else {
                    int temp = min;
                    min = max * A[i];
                    max = temp * A[i];
                }                
            } else {
                min = 0;
                max = 0;
            }
            
            if (max > ret) {
                ret = max;
            }
        }
        
        return ret;
    }

Log in to reply
 

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