43/300
最大子序和 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。思路：DP，“要or不要”+ 存结果。 譬如这道题：[-2,1,-3,4,-1,2,1,-5,4]
lst[0]不动。
当lst[1] = 1，要or不要 [要]：lst[1] = 1 加上 lst[0] = -2 得到-1 [不要]：仍是自己 lst[1] = 1 1 > -1 [不要]的时候数值大于[要]的时候。所以最好的情况就是1，存下来。
当lst[2] = -3， 要or不要 [要]：lst[2] = -3 加上 刚存的lst[1] = 1 得到 -2 [不要]：仍是 lst[2] = -3 -2 > -3，也就是[要]得好，所以最好情况是-2， 存下来。
以此类推。画了个不太好看的表，蓝色是洁身自好的原主[不要]，粉色是[要]，也就是跟前面存下的最优解相加的结果。然后比较蓝粉哪个大。紫色纯是为了好画箭头，把最后一行的比较结果提溜了上来：
class Solution: def maxSubArray(self, nums: List[int]) -> int: for i in range(1, len(nums)): #不用额外申请空间，直接update本位置的决定 nums[i] = max(nums[i] + nums[i-1], nums[i]) return max(nums)优化： 如果最优解存了个负数，走到下一步时，[要](加上这个负数)肯定比[不要](维持原身)要小，看图很明显，对比后大部分粉的，就一个蓝的。所以可以加上一个限定条件：
class Solution: def maxSubArray(self, nums: List[int]) -> int: for i in range(1, len(nums)): if nums[i-1] > 0: nums[i] += nums[i-1] return max(nums)