剑指Offer 42：连续子数组最大和

Leetcode 53. Maximum Subarray

思路比较简单：从前往后累加，当累加和为负数则归零，重新累加；最大和取每次累加和中最大的值。

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

另一个想法是用动态规划：设定为数组结尾为n的连续数组最大和