动态规划-53.最大子数组和-力扣(LeetCode)

一、题目解析

在给定顺序的数组中找出一段具有最大和的连续子数组，且大小最小为1.

二、算法原理

1.状态表示

我们可以意一一枚举出所有的子数组，但我们想要的是最大子数组，所以f[i]表示：以i位置为结尾，所有子数组的最大和

2.状态转移方程

f[i]当长度为1时，此时的子数组和为nums[i]，当长度大于1时，此时的子数组和为[0,i-1]的子数组最大值加上nums[i]，我们需要取二者中的最大值。

所以f[i]=max(nums[i],f[i-1]+nums[i]);

3.初始化

在计算f[i]中我们用到了f[i-1]当i处于0位置时，越界访问，所以我们可以直接初始化f[0]，或者加一个虚拟格子用于初始化。

4.填表顺序

从左到右填表，保证所需值已计算

5.返回值

由于f[i]中存储的是到达i位置的最大子数组和，我们需要知道从[0,n-1] 区间内的最大值，所以返回值为f[i]中的最大值

思考与实践同等重要，在思考后可以去实现一下，链接：53. 最大子数组和 - 力扣（LeetCode）

三、代码示例

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> dp(n+1);for(int i = 1;i<=n;i++){dp[i] = max(nums[i-1],dp[i-1]+nums[i-1]);}int MAX = INT_MIN;//数组中存在负数，所以在比大小时用int的最小值比较，也可以赋值f[1]从2到n开始比较for(int i = 1;i<=n;i++){if(dp[i]>MAX) MAX = dp[i];}return MAX;}
};