1. from typing import List
  4. def MaxSubSum(nums: List[int]) -> int:
  5.     #  dp[i]: 以i结尾的最大字串和
  6.     dp = [None for i in range(len(nums) + 1)]
  7.     dp[0] = float('-INF')
  8.     for i in range(1, len(nums) + 1):
  9.         # 可能出现负数的情况
  10.         dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1])
  12.     return max(dp)
  15. def MaxSubSum1(nums: List[int]) -> int:
  16.     # dp[i], [0, i] 最大字串和
  17.     # dp[i] = max(dp[i-1], max_end_i))
  18.     # 以i为结尾的最长字串和
  20.     max_end_i = []
  21.     dp = []
  22.     for i in range(len(nums)):
  23.         dp[i] = max(dp[i], max_end_i[i])
  24. # nums = [1, 1, -3, 6, 7, -1, 3, 4, -3, -4, -8]
  25. nums = [-3, 1, 3, -1, 2, -4, 2]
  26. print(MaxSubSum(nums))

总结

  • dp 定义问题