Java dp solution with O(1) space and O(n) time


  • 0
    L
     public int maxProduct(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int preMin,preMax;
        int curMin,curMax;
        preMin = preMax = nums[0];
        int res = nums[0];
        for(int i = 1; i < n; i++){
            if(nums[i] >= 0){
                curMin = preMin <= 0 ? preMin*nums[i] : nums[i];
                curMax = preMax > 0 ? preMax*nums[i] : nums[i];
            }
            else{
                curMax = preMin <= 0 ? preMin*nums[i] : nums[i];
                curMin = preMax > 0 ? preMax*nums[i] : nums[i];
            }
            res = Math.max(res,curMax);
            preMin = curMin;
            preMax = curMax;
        }
        return res;
    }

Log in to reply
 

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