最大子数组和

53. 最大子数组和

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

子数组 是数组中的一个连续部分。

class Solution:
  def maxSubArray(self, nums: List[int]) -> int:
      if not nums:
          return 0
      
      dp = [0 for _ in range(len(nums))] ##dp[i]:上一个数组和大于0 到位置i 的数组最大和
      dp[0] = nums[0]
      for i in range(1, len(nums)):
          dp[i] = max(dp[i-1] + nums[i], nums[i])
      return max(dp)