Q53 Maximum Subarray

# 动态规划
class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0 
        maxl = []  # 记录最大子段和
        maxl.append(nums[0])
        for i in range(1, len(nums)):
            if maxl[i-1] < 0 or maxl[i-1] + nums[i] < 0:  # 如果子段和为负值或者子段和加上一个数为负值，则把当前数作为下一个子段和的开始数值
                maxl.append(nums[i])
            else:  # 否则，累积子段和
                maxl.append(maxl[i-1] + nums[i])
        return max(maxl)

a = [-2,1,-3,4,-1,2,1,-5,4]
b = Solution()
print(b.maxSubArray(a))  # 6 # [4,-1,2,1]