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

分析

定义f[i] = what is the max subarray product that ends with index i(inclusive) ?

怎么通过f[j], j < i 来计算f[i]?
假设我们已经知道f[j] (max subarray product that ends with index j)
那么f[i] 要么是f[j] * A[i], 要么是A[i]本身
根据上面这个直白的转移方程，我们写出以下代码

class Solution {
    public int maxProduct(int[] A) {
        int n = A.length, ans = A[0];
        int[] f = new int[n];
        f[0] = A[0];

        for(int i = 1; i < n; i++) {
            f[i] = Math.max(A[i], f[i - 1] * A[i]);
            ans = Math.max(ans, f[i]);
        }
        return ans;
        
    }
}

但是上面这个代码fail了以下test case
这是因为我们没有考虑到这个情况:
A[i] 的前面有一个非常大的负数product subarray，而且A[i]本身也是负数。两者相乘可以得出一个正数的，非常大的数字

Input:
[-2,3,-4]
Output:
3
Expected:
24

经过修改后，程序如下

class Solution {
    public int maxProduct(int[] A) {
        int n = A.length, ans = A[0];
        int[] f = new int[n];
        int[] g = new int[n];
        
        f[0] = A[0];
        g[0] = A[0];

        for(int i = 1; i < n; i++) {
            f[i] = Math.max(A[i], Math.max(f[i - 1] * A[i], g[i - 1] * A[i]));
            g[i] = Math.min(A[i], Math.min(g[i - 1] * A[i], f[i - 1] * A[i]));            
            ans = Math.max(ans, f[i]);
        }
        return ans;
        
    }
}

简化一下空间复杂度，最终代码如下

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