題目
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 來計(jì)算f[i]?
假設(shè)我們已經(jīng)知道f[j] (max subarray product that ends with index j)
那么f[i] 要么是f[j] * A[i], 要么是A[i]本身
根據(jù)上面這個直白的轉(zhuǎn)移方程和二，我們寫出以下代碼

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
這是因?yàn)槲覀儧]有考慮到這個情況:
A[i] 的前面有一個非常大的負(fù)數(shù)product subarray根时，而且A[i]本身也是負(fù)數(shù)漂佩。兩者相乘可以得出一個正數(shù)的澡罚，非常大的數(shù)字

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

經(jīng)過修改后，程序如下

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;
        
    }
}

簡化一下空間復(fù)雜度，最終代碼如下

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;
    }
}