【Java力扣算法】LeetCode 152 乘積最大子序列（動态規劃）

題目：

乘積最大子序列

給定一個整數數組 

nums

 ，找出一個序列中乘積最大的連續子序列（該序列至少包含一個數）。

示例 1:

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

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

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

推薦示例：
[0,2]
[-2]
[-3,-4]
[-1,2,-3]
           

思路：

先定義一個二維dp數組dp[i][0]   dp[i][1]，其中一個用來儲存到目前位置存在的最大值，另一個儲存到目前位置的最小值，因為有負數的存在，是以   最大值和最小值會在遇到負數的時候互換，是以才會儲存兩個值一個最大值一個最小值。因為求的是連續的子序列(這樣的話就不會有跳躍的子集，子集都是連續的)，是以每一次dp隻需要比較上一次dp的最大值與目前位置的乘積的值  和  目前位置的值，它倆誰大就取用誰。最後隻需要取出dp數組中最大的數即可。

代碼：

public static int maxProduct(int[] nums) {
        //dp[i][0]表示到nums[i-1]位置的最大值
        //dp[i][1]表示到nums[i-1]位置的最小值
        int n = nums.length;
        //增加邊界條件
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        //定義一個二維dp數組，用來儲存最大最小值，其中第一個是初始的值 不作為判斷。
        int[][] dp = new int[n + 1][2];
        dp[0][0] = 1;
        dp[0][1] = 1;
        for (int i = 1; i <= n; i++) {
            if (nums[i - 1] < 0) {
                dp[i][0] = Math.max(nums[i - 1], dp[i - 1][1] * nums[i - 1]);
                dp[i][1] = Math.min(nums[i - 1], dp[i - 1][0] * nums[i - 1]);
            } else {
                dp[i][0] = Math.max(nums[i - 1], dp[i - 1][0] * nums[i - 1]);
                dp[i][1] = Math.min(nums[i - 1], dp[i - 1][1] * nums[i - 1]);
            }
        }
        int maxVal = Integer.MIN_VALUE;
        //這是所有的情況都被存在這個dp數組中，隻要周遊找到最大的就可以。
        for (int i = 1; i <= n; i++) {
            maxVal = Math.max(maxVal, dp[i][0]);
        }
        return maxVal;
    }
           

//還有一種解法，不使用dp數組，思路是一樣的，記錄最大最小兩個數值，每次先比較 乘積和目前位置的大小，取最大最小值，每次遇到負數翻轉最大最小值，最後取結果就可以。

public static int maxProduct(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        int result = Integer.MIN_VALUE;
        
        max = 1;
        min = 1;

        for (int i = 0; i < nums.length; i++) {
            //小于0，交換最大最小值。
            if (nums[i] < 0) {
                int tmp = max;
                max = min;
                min = tmp;
            }
            //比較乘積和目前位置的值的大小
            max = Math.max(max * nums[i], nums[i]);
            min = Math.min(min * nums[i], nums[i]);

            result = Math.max(result, max);
        }
        return result;
    }
           

結果：