O(n) dp. O(1) space


  • 0
    U
    class Solution {
        public int maxProduct(int[] nums) {
            if(nums.length==0) return 0;
            
            int minVal = 1;
            int maxVal = 1;
            int oldMax=1;
            int ans =Integer.MIN_VALUE;
            
            for(int i=0; i<nums.length;i++){
                maxVal = Math.max(maxVal*nums[i],Math.max(nums[i],minVal*nums[i]));
                minVal = Math.min(minVal*nums[i], Math.min(nums[i], oldMax*nums[i]));
                oldMax = maxVal;
                ans = Math.max(ans, maxVal);
            }
            
            return ans;
        }
    }
    

Log in to reply
 

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