LeetCode152-乘積最大子數組

題目

給你一個整數數組 nums ，請你找出數組中乘積最大的連續子數組（該子數組中至少包含一個數字），并傳回該子數組所對應的乘積。

輸入: [2,3,-2,4]

輸出: 6

解釋: 子數組 [2,3] 有最大乘積 6。

輸入: [-2,0,-1]

輸出: 0

解釋: 結果不能為 2, 因為 [-2,-1] 不是子數組。

解法

動态規劃：

因為若整個數組都是正數或者有偶數個負數的話，從左到右乘起來是最大值

如果其中有奇數負數的話，從左到右乘起來是最小值

是以解這題的時候我們需要維護兩個數組，目前的最大值，以及最小值，最小值可能為負數，但沒準下一步乘以一個負數，目前的最大值就變成最小值，而最小值則變成最大值了。

注意： 還要考慮0，如果在某個位置是0的話，那麼這個子數組就被截斷了，最大值和最小值要重新統計。

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        int[] maxDp = new int[n];
        int[] minDp = new int[n];
        
        maxDp[0] = nums[0];
        minDp[0] = nums[0];
        int max = maxDp[0];
        for(int i = 1 ; i < n ; ++i){
            int cur = nums[i];
            maxDp[i] = Math.max(cur,Math.max(cur*maxDp[i-1],cur*minDp[i-1]));
            minDp[i] = Math.min(cur,Math.min(cur*maxDp[i-1],cur*minDp[i-1]));
            max = Math.max(max,maxDp[i]);
        }
        return max;
    }
}
           

優化

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        
        int maxDp = nums[0];
        int minDp = nums[0];
        int max = maxDp;
        for(int i = 1 ; i < n ; ++i){
            int cur = nums[i];
            int maxPre = maxDp;
            int minPre = minDp;
            maxDp = Math.max(cur,Math.max(cur*maxPre,cur*minPre));
            minDp = Math.min(cur,Math.min(cur*maxPre,cur*minPre));
            max = Math.max(max,maxDp);
        }
        return max;
    }
}s