Shared O(n) time and O(1) space Solution


  • 0
    L
    public class Solution {
        public int maxProduct(int[] nums) {
            if(nums==null||nums.length<1)return 0;
            if(nums.length==1)return nums[0];
            int product = 0;
            int result = 0;
            int i=0;
            int l = -1;
            int startL = -1;
            boolean productIsSet = false;
            int productLeft = 1;
            int productRight = 1;
            while(i<nums.length){
                if(nums[i]==0){
                    if(!productIsSet){
                        i++;
                        continue;
                    }
                    if(product<0&&i!=startL+1){
                        product = product/Math.max(productLeft,productRight);
                    }
                    result = Math.max(product,result);
                    product = 0;
                    productLeft = 1;
                    productRight = 1;
                    productIsSet = false;
                    l = -1;
                    startL = -1;
                }
                else if(nums[i]>0){
                	if(startL==-1)startL = i;
                    productIsSet = true;
                    if(product==0)product = nums[i];
                    else product*=nums[i];
                    if(productLeft>0)productLeft*=nums[i];
                    else if(productRight<0) productRight*=nums[i];
                }
                else{
                	if(startL==-1)startL = i;
                    productIsSet = true;
                    if(product==0)product = nums[i];
                    else product*=nums[i];
                    if(productLeft>0){
                        productLeft*=nums[i];
                        productRight = nums[i];
                        l = i;
                    }
                    else productRight = nums[i];
                }
                i++;
            }
            if(!productIsSet)return result;
            if(product<0&&i!=startL+1){
                product = product/Math.max(productLeft,productRight);
            }
            else if(product<0&&i==startL+1&&startL!=l){
            	product = product/nums[l];
            }
            if(product==0)return result;
            result = Math.max(product,result);
            return result;
        }
    }

Log in to reply
 

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