152. Maximum Product Subarray.md

Solution1

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = nums[0];
        int preMax = nums[0];
        int preMin = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            int prod1 = nums[i] * preMax;
            int prod2 = nums[i] * preMin;
            preMax = Math.max(nums[i], Math.max(prod1, prod2));
            preMin = Math.min(nums[i], Math.min(prod1, prod2));
            max = Math.max(max, preMax);
        } 
        return max;
    }
}

note

• time O(n) space O(1)
• The idea is to iterate through the array and keep track of three variables: preMax, preMin, max. Why do we need to keep track preMin? Because there are negative numbers in the array, the previous minimum product might be multiplied by a negative number and thus become the maximum. Keeping preMax and preMin, we could swap them if needed. In each iteration, we are actually doing two comparisons.