动态规划19：53. 最大子数组和
动态规划解题步骤：
1.确定状态表示：dp[i]是什么
2.确定状态转移方程：dp[i]等于什么
3.初始化：确保状态转移方程不越界
4.确定填表顺序：根据状态转移方程即可确定填表顺序
5.确定返回值
题目链接：53. 最大子数组和 - 力扣（LeetCode）
题解：
1.状态表示：dp[i]表示以i位置元素为结尾的连续子数组中，最大和连续子数组的元素和
2.状态转移方程：dp[i]=max(dp[i-1]+nums[i],nums[i]) 以i位置元素为结尾的连续子数组有两种情况：一是仅有i位置元素组成一个子数组；二是由i位置元素和前面的元素组成一个子数组
3.初始化：dp[0]=nums[0] 根据状态转移方程，以nums[0]为结尾的子数组只有情况一
4.填表顺序：从左向右填写
5.返回值：返回dp数组中的最大元素，即连续子数组的最大和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//dp[i]表示以i位置元素为结尾的所有连续子数组中最大的子数组和
//dp[i]=max(dp[i-1]+nums[i],nums[i])
size_t n=nums.size();
//处理边界条件
if(n==1) return nums[0];
//创建dp表
vector<int> dp(n);
//初始化
dp[0]=nums[0];
//填表
for(int i=1;i<n;++i)
dp[i]=max(dp[i-1]+nums[i],nums[i]);
//返回值
int ans=-0x3f3f3f3f;
for(auto e:dp) if(e>ans) ans=e;
return ans;
}
};