最大子数组合

12.23 数据结构 eazy
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1

据说是个动态规划的题目，但是目前太菜了，理解不了，题解看了几遍也不能理解，先用一个好理解的方式解题。关键题目本身要求是要连续的子数组，只需要返回最大值就行。因此可以从第一个数开始，逐个相加，用两个变量，一个a保存已发现的最大值，一个b保存当前轮回的最大值，一个轮回结束于当前的值没有贡献后，举个例子只要b还是大于0的，b就是有贡献的，就可以继续加下去，因为你不知道后面还会不会变的更大，并且在这个过程中，每一次的b都需要和已保存的a做对比，已避免错过中途的最大值。关键是当b小于0，也就是没有贡献后，说明上一轮过程中不会再有更大值了，就要从当前的nums[i]开始了

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        top_sum = 0
        max_sum = nums[0]
        for i in range(len(nums)):
            if top_sum + nums[i] >= nums[i]:
                top_sum = top_sum + nums[i]
            else:
                top_sum = nums[i]
            if max_sum < top_sum:
                max_sum = top_sum
            
        return max_sum

更优雅一点可以

max(nums[i],top_sum+nums[i])
max(max_sum,top_sum)