Simple Java code beats 95% O(n) time O(1) space with explanation


  • 0
    M

    The largest product must be one of the situations below:
    1:all the numbers multiply if there are even numbers of negative numbers.
    2:max between (product from the number after first negative number) and (product before the last negative number) if there are odd numbers of negative numbers.
    One thing we have to deal with is if we see 0, we will have to reset all the variable.

        public int maxProduct(int[] nums) {
            int max=Integer.MIN_VALUE,product=1,negative=0,i=0;
            for(i=0;i<nums.length;i++){
                if(nums[i]>max) max=nums[i];
                if(nums[i]==0){ //reset
                    if(negative!=0&&negative!=nums[i-1]) max=Math.max(max,product/negative);
                    negative=0;
                    product=1;
                    continue;
                }
                if((product*=nums[i])>max) max=product;
                if(product<0&&negative==0) negative=product;//memorize the product before(including) first negative numbers we see.
                
            }
            return (negative!=0&&product!=negative)?Math.max(max,product/negative):max;
            //compare product/negative (product after first negative) and max(product before last negative)
        }
    

Log in to reply
 

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