2 Passes scan, beats 99%


  • 23
    Z

    Here are my observations:

    1. it's really about odd negative numbers or even negative numbers, if it's odd, either the left end one or the right end one should be counted, so it will be revealed by scanning from left and from right in 2 passes.
    2. 0 is a kind of delimiter, product accumulation will be reset to 1
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, product = 1;
        int len = nums.length;
    
        for(int i = 0; i < len; i++) {
            max = Math.max(product *= nums[i], max);
            if (nums[i] == 0) product = 1;
        }
    
        product = 1;
        for(int i = len - 1; i >= 0; i--) {
            max = Math.max(product *= nums[i], max);
            if (nums[i] == 0) product = 1;
        }
    
        return max;
    }

  • 0
    D
    This post is deleted!

  • 0
    D

    @zuozuo: your solution will not work for [1.5,0.5,0.3,3,2,0.3,0.5,1.5]


  • 0
    Z

    @divya36 yeah, this approach probably won't work for your input set, since the observation is based on the inputs are integers.


  • 0
    S

    very nice and easy to understand solution. take my upvote.


  • 0
    M

    Great approach, correctly defines the parameters of the pattern. Here is C variant, but attempting the same idea in one single pass.

    int maxProduct(int* nums, int numsSize)
    {
        int i, j, max, tmax1, tmax2, toff;
    
        /* One big loop */
        max = nums[0];
        for (i = 0; i < numsSize; i = j + 1)
        {
            /* Process the array by splitting it into segments divided by
            zero entries. If there are negative numbers, then each segment
            can have up to two sub-array sequences - one which includes the
            first negative number and the other one which does not. */
            for (toff = -1, j = i; j < numsSize && nums[j] != 0; ++j)
            {
                /* Update the product of the first sequence */
                tmax1 = (j == i) ? nums[j] : nums[j] * tmax1;
                max = tmax1 > max ? tmax1 : max;
    
                /* If the second sequence is active , then keep updating
                the product */
                if (toff >= 0) {
                    tmax2 = (toff == j) ? nums[j] : nums[j] *tmax2;
                    max = tmax2 > max ? tmax2 : max;
                }
                /* If this is the first negative value, then mark the beginning
                of the second sub-array sequence. */
                else if (nums[j] < 0)
                    toff = j + 1;
            }
            /* Handle the case where zero is the maximum product. */
            max = (j < numsSize) && max < 0 ? 0 : max;
        }
        /* Return maximum */
        return max;
    }
    

Log in to reply
 

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