[DP]152. Maximum Product Subarra

152. Maximum Product Subarray

虽然和53.很像，但是变成乘法就要考虑一个负负得正的问题。
例子：[2,-3,-2,4]，i=2时，按之前的方法global_max = 2，因为2 *-3 <2。但是实际应该是12。所以不仅要维持到i位置的sub_max,还要维持到i位置的sub_min。
以i结尾的sub_max有三种可能:
Math.max{sub_max * num[i], sub_min * num[i], num[i]}
同理，sub_min也有三种可能 :
Math.min{sub_max * num[i], sub_min * num[i], num[i]}
要注意，更新sub_max以后，更新sub_min时应该用原来的sub_max，所以先保存一个temp。

class Solution {
    public int maxProduct(int[] nums) {
        if(nums.length == 0) return 0;
        int global = nums[0];
        int sub_max = nums[0];
        int sub_min = nums[0];
        for(int i = 1; i<nums.length; i++){
            int last_min = sub_min;
            sub_min = Math.min(Math.min(sub_max * nums[i], sub_min * nums[i]),nums[i]);
            sub_max = Math.max(Math.max(sub_max * nums[i], last_min * nums[i]),nums[i]);

            global = Math.max(sub_max, global);
        }
        return global;
    }
}