题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

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

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解答

动态规划
0 < i < len(nums)，假设f(i)是以nums[i]结尾的连续子数组的最大值
那么问题就可以转换为求，max(f(0), f(1), f(2), ... f(len(nums) - 1))
举个例子，[-2, 1, 3]
对于第1个元素-2，以-2结尾的连续子数组是[-2]，具有最大和的连续子数组是[-2]，最大和-2，f(0) = -2
对于第2个元素1，以1结尾的连续子数组是[1], [-2,1], 具有最大和的连续子数组是[1]，最大和是1，f(1) = 1
对于第3个元素3，以3结尾的连续子数组是[3], [1,3], [-2,1,3]，具有最大和的连续子数组是[1,3]，最大和是4，f(2) = 4
那么整个数组具有最大和的连续子数组是[1,3]，最大和是4

同时，对于f(i)，f(i) = max(f(i-1) + nums[i], nums[i])，
例如对于以第3个元素3结尾的连续子数组，其具有最大和的连续子数组，是以上一个元素1结尾的最大连续子数组[1]加上当前元素3，[1,3]，
所以我们可以从f(0)开始，计算得到f(1)，然后再从f(1)得到f(2)，以此类推，求得所有的0 < i < len(nums)的f(i)
最后得到最大和 max(f(0), f(1), f(2), ... f(len(nums) - 1))

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return
        pre = nums[0]
        ans = nums[0]

        for i in range(1, len(nums)):
            cur = max(pre + nums[i], nums[i])
            ans = max(ans, cur)
            pre = cur
        return ans