Simple Java O(n) time and O(1) space solution with explaination


  • 0
    S
    // Following code finds max continuous product in O(n) time and O(1) space     
    // Iterate over the elements and consider 3 cases
    // If number = 0 then maximum and minimum are zero
    // if number > 0 max = max*number and minimum is either 0 or min*number which ever is smaller
    // if number < 0 min = max*number and maximum is either 0 or max*number which ever is greater 
    public int maxProduct(int[] nums) {
                if(nums.length==0)
                    return 0;
                if(nums.length==1)
                    return nums[0];
                int minimum = 0;
                int maximum = 0;
                int maxsofar = 0;
                for(int i=0;i<nums.length;i++){
                    if(nums[i]==0){
                        minimum = 0;
                        maximum = 0;
                    }
                    else if(nums[i]>0){
                        if(maximum!=0)
                            maximum = maximum*nums[i];
                        else
                            maximum = nums[i];
                        if(minimum!=0)
                            minimum = min(minimum*nums[i],0);
                        else
                            minimum = min(nums[i],0);
                    }
                    else{
                        int temp = maximum;
                        if(minimum!=0)
                            maximum = max(minimum*nums[i],0);
                        else
                            maximum = max(nums[i],0);
                        if(temp!=0)
                            minimum = temp*nums[i];
                        else
                            minimum = nums[i];
                    }
                    if(maxsofar<maximum)
                        maxsofar = maximum;
                }
                return maxsofar;
            }
            
            public int max(int num1, int num2){
                return (num1>num2)?num1:num2;
            }
            
            public int min(int num1, int num2){
                return (num1<num2)?num1:num2;
            }

  • 0
    C

    But this method doesn't fit for the case where the input has float number, correct? So is there any better way that O(n^2) method when float number could be in the array list.?


Log in to reply
 

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