Java 2ms beating 92%, less comparisons


  • 0
    Y

    The solution is very intuitive. I keep updating the max positive product and the max negative product ending at i -1. If they cannot be truly positive or negative, I use 1 instead. Therefore, I can start at index 0, which makes the code more coherent.

    The time saving comes from less comparison. Besides the global max comparison that we all share, the other solutions have 4 comparisons, and I have 2 (one for the outer if, one for deciding whether to set max as 1)

    // O(n) time and O(1) space
    // 2ms, beating 92%
    public int maxProduct(int[] nums) {
        int maxPosProd = 1; // positive product ending at i - 1, with max abs value
        int maxNegProd = 1; // negative product ending at i - 1, with max abs value
        int globalMax = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int max = nums[i];
            if (nums[i] < 0) {
                max *= maxNegProd;
                maxNegProd = maxPosProd * nums[i];
                maxPosProd = max > 0 ? max : 1;
            } else if (nums[i] > 0) {
                max *= maxPosProd;
                maxPosProd = max;
                maxNegProd = maxNegProd < 0 ? maxNegProd * nums[i] : 1;
            } else { // nums[i] == 0, reset
                maxPosProd = 1;
                maxNegProd = 1;
            }
            globalMax = Math.max(globalMax, max);
        }
        return globalMax;
    }

Log in to reply
 

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