动态规划。  其子问题可以为：以第i个元素为结尾的具有最大和的连续子数组。

为此，建立一个与原数组A同样长度的数组B，其每个位置B[i]保存以A[i]为结尾的连续子数组的最大和。

数组B中的最大值即为原问题所求。

 

子问题的递归求解方式：

如果B[i-1]>0，则直接将A[i]补在其后就得到了以A[i]为结尾的连续子数组的最大和；

否则，说明需要把A[i-1]之前丢掉，仅A[i]一个数就构成了以A[i]为结尾的连续子数组的最大和。

 

python

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        B = [nums[0]]
        for i in range(1,len(nums)):
            if B[i-1] >= 0:
                B.append(B[i-1]+nums[i])
            else:
                B.append(nums[i])
        return max(B)