目錄

動態規劃怎么學？

1. 題目解析

2. 算法原理

1. 狀態表示

2. 狀態轉移方程

3. 初始化

4. 填表順序

5. 返回值

3. 代碼編寫

寫在最后：

---

動態規劃怎么學？

學習一個算法沒有捷徑，更何況是學習動態規劃，

跟我一起刷動態規劃算法題，一起學會動態規劃！

1. 題目解析

題目鏈接：918. 環形子數組的最大和 - 力扣（LeetCode）

這道題目巴拉巴拉說了一大堆好像很玄乎的東西，我們不管他，

抓住題目的核心是要找子數組，那找子數組的規則是什么呢？

我們直接通過看示例來解讀：

通過示例二，我們可以看出什么叫做環形數組，他的頭和尾是相連的，

所以 5 和 5 可以組成一個子數組。

那我們該怎么做這道題呢？

我們可以將它拆解成兩個子問題：

1. 就是正常求他的最大子數組：

2. 因為環形數組的原因，我們可以將首尾相連的情況轉化成求最小子數組和的情況：

2. 算法原理

1. 狀態表示

根據我們上面分析的兩種情況，其實就可以氛圍兩種狀態表示：

f [ i ] 表示以 i 為結尾的所有子數組的最大和

g [ i ] 表示以 i 為結尾的所有子數組的最小和?

2. 狀態轉移方程

然后每個狀態表示有兩種情況，一個種情況是自己，一種情況是自己加上上一個位置的最大/小和

所以他們的狀態轉移方程是：

f [ i ] = max( nums[ i ]，nums[ i ] + f [ i - 1 ]?)

g [ i ] = min( nums[ i ]，nums[ i ] + g[ i - 1]?)

3. 初始化

初始化時為了防止越界，多加一格然后初始化成0即可

4. 填表順序

從左往右

5. 返回值

max( f 數組的最大值，sum - g 數組的最小值?)

3. 代碼編寫

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();vector<int> f(n + 1);auto g = f;for(int i = 1; i <= n; i++) {f[i] = max(nums[i - 1], nums[i - 1] + f[i - 1]);g[i] = min(nums[i - 1], nums[i - 1] + g[i - 1]);}int fmax = INT_MIN;int gmin = INT_MAX;int sum = 0;for(int i = 1; i <= n; i++) fmax = max(fmax, f[i]);for(int i = 1; i <= n; i++) gmin = min(gmin, g[i]);for(auto s : nums) sum += s;return fmax < 0 ? fmax : max(fmax, sum - gmin);}
};

寫在最后：

以上就是本篇文章的內容了，感謝你的閱讀。

如果感到有所收獲的話可以給博主點一個贊哦。

如果文章內容有遺漏或者錯誤的地方歡迎私信博主或者在評論區指出~