152. Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

dynamic programming, use a int to keep track of minimal product of subarrays

dp[i+1] = Math.max(nums[i+1], dp[i]*nums[i+1], preMin*nums[i+1]);

class Solution {
    public int maxProduct(int[] nums) {
        // let dp[i] be the largest product of subarray end at index of i
        // let preMin be the smallest product of subarray end at index of i
        // dp[i+1] = Math.max(nums[i+1], dp[i]*nums[i+1], preMin*nums[i+1]);
        
        // use int to record min prodction
        int preMin = nums[0];
        // use nums[] to record max production
        
        int res = nums[0];
        for (int i=1; i<nums.length; i++){
            int min = Math.min(preMin*nums[i], nums[i-1]*nums[i]);        
            int max = Math.max(preMin*nums[i], nums[i-1]*nums[i]);
            preMin = Math.min(nums[i], min);
            
            nums[i] = Math.max(nums[i], max);                        
            res = nums[i]>res ? nums[i] : res;
            
        }
        return res;
    }
}