My O(n) java solution, beats 96 % of Java Submissions


  • 0
    K
    public int maxProduct(int[] nums) {
            int n= nums.length;
            if(n==0) return 0;
            int prod=1,sol=Integer.MIN_VALUE;
            for(int i=0;i<n;i++){
                
                    prod =prod * nums[i];
                    if(prod > sol) sol = prod;
                    if(nums[i]==0) prod =1;
                }
                
            
            prod =1;
            for(int i=n-1;i>=0;i--){
                
                    prod = prod *nums[i];
                    if(prod >sol) sol = prod;
                     if(nums[i]==0) prod =1;
            }
            return sol;
    

    The logic here is that if there are odd number of negative values, then either the first negative or last negative has to be discarded from the total array and we will get the max product from the remaining sub array.

    That is why we make two passes, one from the beginning and other from the end. So that we will compute max product of sub array from both sides and see discarding which negative value will give us the best answer.

    And of course, the case of an element being zero has to be considered and code should be changed appropriately.


Log in to reply
 

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