【学会动态规划】最大子数组和（19）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】最大子数组和（19）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：53. 最大子数组和 - 力扣（LeetCode）

【学会动态规划】最大子数组和（19）,学会动态规划,动态规划,算法

题目很好理解，顾名思义，就是找最大的子数组和。

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;
    }
};