🎋前言

動態(tài)規(guī)劃相關(guān)題目都可以參考以下五個步驟進行解答：

1. 狀態(tài)表示

2. 狀態(tài)轉(zhuǎn)移?程

3. 初始化

4. 填表順序

5. 返回值

后面題的解答思路也將按照這五個步驟進行講解。

🎋最大子數(shù)組和

🚩題目描述

給你一個整數(shù)數(shù)組 nums ，請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

子數(shù)組是數(shù)組中的一個連續(xù)部分。

• 示例 1：
  輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
  輸出：6
  解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 。
• 示例 2：
  輸入：nums = [1]
  輸出：1
• 示例 3：
  輸入：nums = [5,4,-1,7,8]
  輸出：23

class Solution {public int maxSubArray(int[] nums) {}
}

🚩算法思路

1. 狀態(tài)表示：

對于線性 dp ，我們可以?「經(jīng)驗 + 題?要求」來定義狀態(tài)表示：

• 以某個位置為結(jié)尾，進行一系列操作；
• 以某個位置為起點，進行一系列操作。

這?我們選擇比較常用的方式，以「某個位置為結(jié)尾」，結(jié)合「題目要求」，定義?個狀態(tài)表示：

dp[i] 表?：以 i 位置元素為結(jié)尾的「所有?數(shù)組」中和的最?和。

2. 狀態(tài)轉(zhuǎn)移?程：

dp[i] 的所有可能可以分為以下兩種：

• 子數(shù)組的長度為 1 ：此時 dp[i] = nums[i] ；
• 子數(shù)組的長度?大于 1 ：此時 dp[i] 應(yīng)該等于 以 i - 1 做結(jié)尾的「所有?數(shù)組」中和 的最?值再加上 nums[i] ，也就是 dp[i - 1] + nums[i] 。

由于我們要的是「最大值」，因此應(yīng)該是兩種情況下的最?值，因此可得轉(zhuǎn)移?程：

• dp[i] = max(nums[i], dp[i - 1] + nums[i]) 。

3. 初始化：

可以在最前?加上?個「輔助結(jié)點」，幫助我們初始化。使用這種技巧要注意兩個點：

• 輔助結(jié)點里面的值要「保證后續(xù)填表是正確的」；
• 「下標(biāo)的映射關(guān)系」。

在本題中，最前?加上?個格?，并且讓 dp[0] = 0 即可。

4. 填表順序

根據(jù)「狀態(tài)轉(zhuǎn)移?程」易得，填表順序為「從左往右」。

5. 返回值：

狀態(tài)表示為「以 i 為結(jié)尾的所有?數(shù)組」的最?值，但是最大子數(shù)組和的結(jié)尾我們是不確定的。

因此我們需要返回整個 dp 表中的最?值。

🚩代碼實現(xiàn)

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length + 1];int ret = Integer.MIN_VALUE;for (int  i = 1; i < dp.length; i++) {dp[i] = Math.max(nums[i -1],dp[i - 1] + nums[i - 1]);ret = Math.max(ret,dp[i]);}return ret;}
}

🌴環(huán)形子數(shù)組的最大和

🚩題目描述

給定一個長度為 n 的環(huán)形整數(shù)數(shù)組 nums ，返回 nums 的非空 子數(shù)組 的最大可能和 。

環(huán)形數(shù)組 意味著數(shù)組的末端將會與開頭相連呈環(huán)狀。形式上， nums[i] 的下一個元素是 nums[(i + 1) % n] ， nums[i] 的前一個元素是 nums[(i - 1 + n) % n] 。

子數(shù)組 最多只能包含固定緩沖區(qū) nums 中的每個元素一次。形式上，對于子數(shù)組 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

• 示例 1：
  輸入：nums = [1,-2,3,-2]
  輸出：3
  解釋：從子數(shù)組 [3] 得到最大和 3
• 示例 2：
  輸入：nums = [5,-3,5]
  輸出：10
  解釋：從子數(shù)組 [5,5] 得到最大和 5 + 5 = 10
• 示例 3：
  輸入：nums = [3,-2,2,-3]
  輸出：3
  解釋：從子數(shù)組 [3] 和 [3,-2,2] 都可以得到最大和 3

class Solution {public int maxSubarraySumCircular(int[] nums) {}
}

🚩算法思路：

本題與「最大子數(shù)組和」的區(qū)別在于，考慮問題的時候不僅要分析「數(shù)組內(nèi)的連續(xù)區(qū)域」，還要考慮「數(shù)組?尾相連」的?部分。結(jié)果的可能情況分為以下兩種：

1. 結(jié)果在數(shù)組的內(nèi)部，包括整個數(shù)組；
2. 結(jié)果在數(shù)組首尾相連的?部分上。

其中，對于第?種情況，我們僅需按照「最大子數(shù)組和」的求法就可以得到結(jié)果，記為 fmax 。

對于第?種情況，我們可以分析?下：

• 如果數(shù)組?尾相連的?部分是最?的數(shù)組和，那么數(shù)組中間就會空出來?部分；
• 因為數(shù)組的總和 sum 是不變的，那么中間連續(xù)的?部分的和?定是最小的；

因此，我們就可以得出?個結(jié)論，對于第?種情況的最?和，應(yīng)該等于 sum - gmin ，其中g(shù)min 表?數(shù)組內(nèi)的「最??數(shù)組和」。

兩種情況下的最?值，就是我們要的結(jié)果。

但是，由于數(shù)組內(nèi)有可能全部都是負(fù)數(shù)，第?種情況下的結(jié)果是數(shù)組內(nèi)的最?值（是個負(fù)數(shù)），第?種情況下的 gmin == sum ，求的得結(jié)果就會是 0 。

若直接求兩者的最?值，就會是 0 。但是實際的結(jié)果應(yīng)該是數(shù)組內(nèi)的最?值。對于這種情況，我們需要特殊判斷?下。

由于「最??數(shù)組和」的?法已經(jīng)講過，這?只提?下「最??數(shù)組和」的求解過程，其實與「最??數(shù)組和」的求法是?致的。? f 表?最?和， g 表?最?和。

1. 狀態(tài)表示：

g[i] 表?：以 i 做結(jié)尾的「所有?數(shù)組」中和的最?值。

2. 狀態(tài)轉(zhuǎn)移?程：

g[i] 的所有可能可以分為以下兩種：

1. ?數(shù)組的?度為 1 ：此時 g[i] = nums[i] ；
2. ?數(shù)組的?度?于 1 ：此時 g[i] 應(yīng)該等于 以 i - 1 做結(jié)尾的「所有?數(shù)組」中和的最?值再加上 nums[i] ，也就是 g[i - 1] + nums[i] 。

由于我們要的是最??數(shù)組和，因此應(yīng)該是兩種情況下的最?值，因此可得轉(zhuǎn)移?程：

• g[i] = min(nums[i], g[i - 1] + nums[i]) 。

3. 初始化：
   可以在最前?加上?個輔助結(jié)點，幫助我們初始化。使?這種技巧要注意兩個點：

• 輔助結(jié)點??的值要保證后續(xù)填表是正確的；

• 下標(biāo)的映射關(guān)系。

在本題中，最前?加上?個格?，并且讓 g[0] = 0 即可。

4. 填表順序：

根據(jù)狀態(tài)轉(zhuǎn)移?程易得，填表順序為「從左往右」。

5. 返回值：

• 先找到 f 表??的最?值 -> fmax ；
• 找到 g 表??的最?值 -> gmin ；
• 統(tǒng)計所有元素的和 -> sum ；
• 返回 sum == gmin ? fmax : max(fmax, sum - gmin)

🚩代碼實現(xiàn)

    public int maxSubarraySumCircular(int[] nums) {// 1. 創(chuàng)建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int n = nums.length;int[] f = new int[n + 1];int[] g = new int[n + 1];int sum = 0;int fmax = Integer.MIN_VALUE;int gmin = Integer.MAX_VALUE;for(int i = 1; i <= n; i++) {int x = nums[i - 1];f[i] = Math.max(x, x + f[i - 1]);fmax = Math.max(fmax, f[i]);g[i] = Math.min(x, x + g[i - 1]);gmin = Math.min(gmin, g[i]);sum += x;}return sum == gmin ? fmax : Math.max(fmax, sum - gmin);}

🌲乘積最大子數(shù)組

🚩題目描述

給你一個整數(shù)數(shù)組 nums ，請你找出數(shù)組中乘積最大的非空連續(xù)

子數(shù)組（該子數(shù)組中至少包含一個數(shù)字），并返回該子數(shù)組所對應(yīng)的乘積。

測試用例的答案是一個 32-位 整數(shù)。

• 示例 1:
  輸入: nums = [2,3,-2,4]
  輸出: 6
  解釋: 子數(shù)組 [2,3] 有最大乘積 6。
• 示例 2:
  輸入: nums = [-2,0,-1]
  輸出: 0
  解釋: 結(jié)果不能為 2, 因為 [-2,-1] 不是子數(shù)組。

class Solution {public int maxProduct(int[] nums) {}
}

🚩算法思路：

這道題與「最大子數(shù)組和] 非常相似，我們可以效仿著定義?下狀態(tài)表?以及狀態(tài)轉(zhuǎn)移：

• dp[i] 表示以 i 為結(jié)尾的所有子數(shù)組的最?乘積，
• dp[i] = max(nums[i], dp[i - 1] * nums[i]) ；

由于正負(fù)號的存在，我們很容易就可以得到，這樣求 dp[i] 的值是不正確的。因為 dp[i - 1] 的信息并不能讓我們得到 dp[i] 的正確值。

比如數(shù)組 [-2, 5, -2] ，用上述狀態(tài)轉(zhuǎn)移得到的 dp數(shù)組為 [-2, 5, -2] ，最?乘積為 5 。但是實際上的最?乘積應(yīng)該是所有數(shù)相乘，結(jié)果為 20 。

究其原因，就是因為我們在求 dp[2] 的時候，因為 nums[2] 是?個負(fù)數(shù)，因此我們需要的是「 i - 1 位置結(jié)尾的最?的乘積 （-10） 」，這樣?個負(fù)數(shù)乘以「最?值」，才會得到真實的最?值。

因此，我們不僅需要?個「乘積最?值的 dp 表」，還需要?個「乘積最?值的 dp 表」。

1. 狀態(tài)表?：

f[i] 表?：以 i 結(jié)尾的所有?數(shù)組的最?乘積，
g[i] 表?：以 i 結(jié)尾的所有?數(shù)組的最?乘積。

2. 狀態(tài)轉(zhuǎn)移?程：

遍歷每?個位置的時候，我們要同步更新兩個 dp 數(shù)組的值。

對于 f[i] ，也就是「以 i 為結(jié)尾的所有?數(shù)組的最?乘積」，對于所有?數(shù)組，可以分為下?三種形式：

• ?數(shù)組的?度為 1 ，也就是 nums[i] ；
• ?數(shù)組的?度?于 1 ，但 nums[i] > 0 ，此時需要的是 i - 1 為結(jié)尾的所有?數(shù)組的最?乘積 f[i - 1] ，再乘上 nums[i] ，也就是 nums[i] * f[i - 1] ；
• ?數(shù)組的?度?于 1 ，但 nums[i] < 0 ，此時需要的是 i - 1 為結(jié)尾的所有?數(shù)組的最?乘積 g[i - 1] ，再乘上 nums[i] ，也就是 nums[i] * g[i - 1] ；（如果 nums[i] = 0 ，所有?數(shù)組的乘積均為 0 ，三種情況其實都包含了）

綜上所述， f[i] = max(nums[i], max(nums[i] * f[i - 1], nums[i] * g[i -
1]) )。

對于 g[i] ，也就是「以 i 為結(jié)尾的所有?數(shù)組的最?乘積」，對于所有?數(shù)組，可以分為下?三種形式：

• 子數(shù)組的?度為 1 ，也就是 nums[i] ；
• 子數(shù)組的?度?于 1 ，但 nums[i] > 0 ，此時需要的是 i - 1 為結(jié)尾的所有子數(shù)組的最?乘積 g[i - 1] ，再乘上 nums[i] ，也就是 nums[i] * g[i - 1] ；
• 子數(shù)組的長度度?于 1 ，但 nums[i] < 0 ，此時需要的是 i - 1 為結(jié)尾的所有子數(shù)組的最?乘積 f[i - 1] ，再乘上 nums[i] ，也就是 nums[i] * f[i - 1] ；

綜上所述， g[i] = min(nums[i], min(nums[i] * f[i - 1], nums[i] * g[i - 1])) 。
（如果 nums[i] = 0 ，所有?數(shù)組的乘積均為 0 ，三種情況其實都包含了）

3. 初始化：

可以在最前面加上?個輔助結(jié)點，幫助我們初始化。使?這種技巧要注意兩個點：

• 輔助結(jié)點里面的值要保證后續(xù)填表是正確的；
• 下標(biāo)的映射關(guān)系。

在本題中，最前?加上?個格?，并且讓 f[0] = g[0] = 1 即可。

4. 填表順序：

根據(jù)狀態(tài)轉(zhuǎn)移?程易得，填表順序為「從左往右，兩個表?起填」。

5. 返回值：

返回 f 表中的最?值

🚩代碼實現(xiàn)

class Solution {public int maxProduct(int[] nums) {// 1. 創(chuàng)建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int n = nums.length;int[] f = new int[n + 1];int[] g = new int[n + 1];f[0] = 1;g[0] = 1;int ret = Integer.MIN_VALUE;for(int i = 1; i <= n; i++) {int x = nums[i - 1];int y = f[i - 1] * nums[i - 1];int z = g[i - 1] * nums[i - 1];f[i] = Math.max(x, Math.max(y, z));g[i] = Math.min(x, Math.min(y, z));ret = Math.max(ret, f[i]);}return ret;}
}

?總結(jié)

關(guān)于《【算法優(yōu)選】 動態(tài)規(guī)劃之子數(shù)組、子串系列——壹》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評指正，如果文章對您有幫助或者覺得作者寫的還不錯可以點一下關(guān)注，點贊，收藏支持一下！