[数据结构与算法]剑指 Offer 42. 连续子数组的最大和

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

利用动态规划的思想

1.注意负数加上当前位置，dp只会减小，故应该排除。

2.还需要max去保存加上当前位置和之前最大值的对比。