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.

刚看完覃超的直播。他说先不要用野路子dp，先老实开辟一个维度。
这题为什么要开辟一个新维度呢，因为这题要维护上一个最优值是max positive和min negtive两种情况。

public class Solution {
    //dp[index][正负]
    //dp[i][0] = dp[i-1][0] * nums[i] (nums[i]>=0)    or    dp[i-1][1] * nums[i](nums[i]<0)
    //dp[i][1] = dp[i-1][1] * nums[i] (nums[i]>=0)    or    dp[i-1][0] * nums[i](nums[i]<0)
    public int maxProduct(int[] nums) {
        if (nums.length==0) return 0;
        int dp[][] = new int[nums.length][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];
        int res = nums[0] ;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= 0) {
                dp[i][0] = dp[i - 1][0] * nums[i];
                dp[i][1] = dp[i - 1][1] * nums[i];
            } else {
                dp[i][0] = dp[i - 1][1] * nums[i];
                dp[i][1] = dp[i - 1][0] * nums[i];
            }

            dp[i][0] = Math.max(dp[i][0] , nums[i]);
            dp[i][1] = Math.min(dp[i][1] , nums[i]);
            res = Math.max(res,dp[i][0]);
        }
        return res;
    }
}

他这种写法，理解起来并不简单。。同样涉及到local跟global的那种原理。至少我现在很晕，可能因为很困了。12点多了还在公司，日。这题还可以状态压缩。

对于这种dp，还是要找时间跟code ganker那种local global的「野路子」（其实我觉得他那种也不算野路子，也是一种套路）都好好理一遍。

12/04/2017更新

刚才又看了一遍这个题，重新定义了一遍状态：

nums[i]>=0 ：
dpPos[i] = dpPos[i-1] * nums[i] 这里dpPos只存放positive max的值
dpNeg[i] = dpNeg[i-1] * nums[i] 这里dpMin只存放negative min的值
nums[i]<0 ：
dpNeg[i] = dpPos[i-1] * nums[i] 这里dpPos只存放positive max的值
dpPos[i] = dpNeg[i-1] * nums[i] 这里dpMin只存放negative min的值

这个方程对应的解法，九章上有：http://www.jiuzhang.com/solutions/maximum-product-subarray/

用野路子的空间轮换做了一遍，没有分开两个数组，而是只用了max min两个变量存储：

    public int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;
        int res = nums[0];

        int maxPos = nums[0];
        int minNeg = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= 0) {
                maxPos = maxPos * nums[i];
                minNeg = minNeg * nums[i];
            } else {
                int minNegCopy = minNeg;
                minNeg = maxPos * nums[i];
                maxPos = minNegCopy * nums[i];
            }
            maxPos = Math.max(maxPos, nums[i]);
            minNeg = Math.min(minNeg, nums[i]);
            res = Math.max(maxPos, res);
        }
        return res;
    }

这里注意那个Math.max在比较maxPos和minNeg的时候也要跟当前数字对比，我一开始不懂，后来了解到因为如果给这两个变量都初始化nums[0]的话，这样做就有道理了。还有，由于没有采用数组，这里需要创建一个minNegCopy。

code ganker的 local global解法：

public int maxProduct(int[] A) {
    if(A==null || A.length==0)
        return 0;
    if(A.length == 1)
        return A[0];
    int max_local = A[0];
    int min_local = A[0];
    int global = A[0];
    for(int i=1;i<A.length;i++)
    {
        int max_copy = max_local;
        max_local = Math.max(Math.max(A[i]*max_local, A[i]), A[i]*min_local);
        min_local = Math.min(Math.min(A[i]*max_copy, A[i]), A[i]*min_local);
        global = Math.max(global, max_local);
    }
    return global;
}

他这边都没有判断nums[i]正负了，而是把三个数一起比较，很聪明。