目錄

動態規劃怎么學？

1. 題目解析

2. 算法原理

1. 狀態表示

2. 狀態轉移方程

3. 初始化

4. 填表順序

5. 返回值

3. 代碼編寫

寫在最后：

---

動態規劃怎么學？

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

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

1. 題目解析

題目鏈接：53. 最大子數組和 - 力扣（LeetCode）

題目很好理解，顧名思義，就是找最大的子數組和。

2. 算法原理

1. 狀態表示

dp [ i ] 位置表示以 i 位置元素為結尾的所有子數組的最大和。

2. 狀態轉移方程

狀態轉移方程有兩種情況，

1. 子數組長度為 1 時，最大和就是 i 位置的值

2. 子數組長度大于 1 是，最大和就是上一個位置的最大和 + 當前位置的值

所以我們就可以得出狀態轉移方程

dp [ i ] = max( nums[ i ]，dp[ i ] + nums[ i ] )

3. 初始化

初始化就是防止越界，并且不影響后面的值，

初始化成 0 即可。

4. 填表順序

從左往右即可。

5. 返回值

返回整個 dp 表里的最大值。

3. 代碼編寫

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> dp(n + 1);int ans = INT_MIN;for(int i = 1; i <= n ; i++) {dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);ans = max(ans, dp[i]);}return ans;}
};

寫在最后：

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

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

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