Java Two pointers O(n) solution


  • 0

    The basic idea is that we just need compute prefix and suffix of the array. If there is 0 in the array, we treat it as a new beginning.

    public int maxProduct(int[] nums) {
            if(nums.length==0) return 0;
            int low = 0, high = 0, ans = Integer.MIN_VALUE, pi = 1;
            while(low<nums.length){
                while(high<nums.length&&nums[high]!=0){
                    pi *= nums[high];
                    ans = Math.max(ans,pi);
                    high++;
                }
                while(low<high){
                    pi /= nums[low];
                    if(low!=high-1) ans = Math.max(ans,pi);
                    low++;
                }
                if(high<nums.length&&nums[high] == 0){
                    ans = Math.max(ans,0);
                    high++;
                    low++;
                }
            }
            return ans;
        }
    

Log in to reply
 

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