[編程題] lk [152. 乘積最大子數組-二維動態規劃]

標簽：一維數組   最大子數組   info   block   color   dpm   str   lan   本質   

[編程題] lk 152. 乘積最大子數組-二維動態規劃

題目

輸入輸出

方法1：使用一個二維的dp來表示當前節點的最大值和最小值情況

思想：

? 每個dp[i]位置用兩個維度表示值信息，dp[i][0]表示目前的最大值情況,dp[i][1]表示目前的最小值情況如負數
? ① 我們在遍歷數組的時候，如果碰到nums[i]是負數，那么我們拿出上一個狀態dp[i]的最小值即dp[i][1]得出的結果一定是正,這樣子的情況最大；

? ② 我們在遍歷數組的時候，如果碰到nums[i]是正數，那么我們拿出上一個狀態dp[i]的最大值即dp[i][0]得出的結果一定是正,這樣子的情況最大、

總結來說，我們算當前的dp【i】【0】即是算最大值，即求

max(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i], nums[i])

總結來說，我們算當前的dp【i】【1】即是算最小值，即求

mix(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i], nums[i])

方法：動態規劃（二維dp）

class Solution {
    //方法1：動態規劃(使用二維數組表示dp狀態)
    public int maxProduct(int[] nums) {
        int[][] dp = new int[nums.length][2];  //其中的0維度表示該數為止的max值，1維度表示該數為止的最小值
        dp[0][0] = nums[0]; //默認dp[0]最大值
        dp[0][1] = nums[0]; //默認dp[0]最小值
        int max = dp[0][0]; //記錄最大值
        for(int i=1;i<nums.length;i++){
            //本質是max(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i], nums[i]),Java API只能接收倆參數
            dp[i][0] = Math.max(dp[i-1][0]*nums[i], Math.max(dp[i-1][1]*nums[i], nums[i])); //最大值
            dp[i][1] = Math.min(dp[i-1][0]*nums[i], Math.min(dp[i-1][1]*nums[i], nums[i])); //最小值
            max = Math.max(max, dp[i][0]);
        }
        return max;
    }
}

方法2：我們用兩個dp[]一維數組來表示當前狀態的最大值和最小值數組

思想：

? 本質和上述沒區別，只是我們分了兩個dp[]一維數組來分別表達dp[i]的max和min,在計算的時候也是類似上邊的情況得到最大最小值。

Java代碼

//方法2：我們用兩個dp[]一維數組來表示當前狀態的最大值和最小值數組
    public int maxProduct(int[] nums) {
        int[] dpMax = new int[nums.length];  //表示當前節點的最大值
        int[] dpMin = new int[nums.length];  //表示當前節點的最小值

        dpMax[0] = nums[0]; //最大值的首節點
        dpMin[0] = nums[0]; //最小值的首節點

        int max = nums[0]; //默認的最大值
        for(int i=1;i<nums.length;i++){
            dpMax[i] = Math.max(dpMax[i-1]*nums[i],Math.max(dpMin[i-1]*nums[i],nums[i]));
            dpMin[i] = Math.min(dpMax[i-1]*nums[i],Math.min(dpMin[i-1]*nums[i],nums[i]));
            max = max>dpMax[i]?max:dpMax[i];
        }
        return max;
    }

輸出：

[編程題] lk [152. 乘積最大子數組-二維動態規劃]

標簽：一維數組   最大子數組   info   block   color   dpm   str   lan   本質   

原文地址：https://www.cnblogs.com/jiyongjia/p/13405963.html