最大子序和（LeetCode-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
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
思路
五部曲
dp[i] 含义
包含下标 i ii 的最大连续子数组和
递推公式
前面的最大和加上当前元素的值首先必须是正的才有积极意义，其次如果小于当前元素值，那么当前元素就没有必要带前面的一起，不如自己当头元素
d p [ i ] = m a x ( d p [ i − 1 ] + n u m s [ i ] , n u m s [ i ] )
数组初始化
dp[0] 应该等于 n u m s [ 0 ]
遍历顺序
从前往后
测试用例
代码展示
class Solution { public: int maxSubArray(vector<int> &nums) { int n = nums.size(); vector<int> dp(n); dp[0] = nums[0]; int result = dp[0]; for (int i = 1; i < n; i++) { dp[i] = max(dp[i - 1] + nums[i], nums[i]); result = max(result, dp[i]); } return result; } };
