10.1 动态规划
53.最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
解答：遍历一次，求出以每个元素结尾的最大和。对于每个元素，如果该元素之前元素的最大和<0，那么该元素的最大和为自己。否则为最大和 + 自己。记录一每个元素为结尾的最大值。
int maxSubArray(vector<int> &nums)
{
int pre = 0, ans = 0;
for (auto &num : nums)
{
pre = max(pre + num, num);
ans = max(ans, pre);
}
}