乘积最大子序列 -dp

找出一个序列中乘积最大的连续子序列（至少包含一个数）。

样例
样例 1:

输入:[2,3,-2,4]
输出:6
样例 2:

输入:[-1,2,4,1]
输出:8
注意事项
数组长度不超过20000
乘积最大的子序列的积，小于2147483647

    /**
     * a[j]
     * a[j-1]*a[j]
     * if a[j]>0 a[j-1] most max
     * if a[j]<0 a[j-1] most min
     * <p>
     * f[j] most max
     * g[j] most min
     * <p>
     * f[j] = max{ a[j], max{ a[j]*f[j-1]],a[j]]*f[j-1] } }
     * g[j] = min{ a[j], min{ a[j]*f[j-1]],a[j]]*f[j-1] } }
     *
     * @param nums: An array of integers
     * @return: An integer
     */
    public static int maxProduct(int[] nums) {
        // write your code here
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] f = new int[n];
        int[] g = new int[n];
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                f[i] = nums[i];
                g[i] = nums[i];
            } else {
                f[i] = Math.max(nums[i], Math.max(nums[i] * f[i - 1], nums[i] * g[i - 1]));
                g[i] = Math.min(nums[i], Math.min(nums[i] * f[i - 1], nums[i] * g[i - 1]));
            }
            res = Math.max(res, f[i]);
        }
        return res;
    }