152. Maximum Product Subarray (1d-dp)

1. 其實有 0 或 奇數個neg 時應該要重新選擇起始點, 所以要跟 nums[i] 比較

2. 偶數個 neg 時可能會產生 max 值, 解法是紀錄 max 和 min value, 如果neg*neg 時就會產生 max 值

idea -

max( max product, min product, current value),

min( max product, min product, current value),

because of negative*negative may generate max number!

最後取最大值

time: O(n)

space: O(1)

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int temp = max;
            max = Math.max(Math.max(nums[i]*max, nums[i]*min), nums[i]);
            min = Math.min(Math.min(nums[i]*temp, nums[i]*min), nums[i]);
            res = Math.max(res, max);
        }
        return res;
    }
}

original DP

class Solution {
    public int maxProduct(int[] nums) {
        // [-2,0,-1], max = 0, 
        // 2 3 -3 4  max = 6
        // 2 -3 -3 4 max = 72 , so when even neg, will have max value
        // 2 -3 [-3 4 -3 -2 1 -4] max =  36* 8
        int dpMax[] = new int[nums.length];
        int dpMin[] = new int[nums.length];

        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        int res = nums[0];

        for (int i = 1; i < nums.length; i++) {
            dpMax[i] = Math.max(Math.max(nums[i]*dpMax[i-1], nums[i]*dpMin[i-1]), nums[i]) ;
            dpMin[i] = Math.min(Math.min(nums[i]*dpMax[i-1], nums[i]*dpMin[i-1]), nums[i]);
            res = Math.max(res, dpMax[i]);
        }
        return res;
    }
}

then use variables, or like first one way

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        int res = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int newMax = Math.max(Math.max(nums[i]*max, nums[i]*min), nums[i]) ;
            int newMin = Math.min(Math.min(nums[i]*max, nums[i]*min), nums[i]);
            max = newMax;
            min = newMin;
            res = Math.max(res, max);
        }
        return res;
    }
}