Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

一刷
题解：求最大乘积子数组。 依然是用Dynamic Programming的思想，不过这回我们要维护一个max以及一个min。注意，当当前num[i]为负数时，max和min交换。
Time Complexity - O(n)， Space Complexity - O(1)。

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

二刷
首先思考，当长度增1，是不是可以利用之前的解，如果可以的话，就是DP问题。
之前的解，最大值和最小值都要保存下来，因为如果当前是负数，那么最大值就变成了最小值。

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