【PYTHON】力扣刷题笔记 -- 0053. 最大子数组和【中等】

• 子数组（最少包含一个元素）: 是数组中的一个连续部分

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6

示例 2:
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

1. 确定 dp 数组含义：dp[i] 表示包括下标 i（以 nums[i] 为结尾）的最⼤连续⼦序列和
   • 注意❌不能表示 nums[: i+1] 的最⼤连续⼦序列和 (不一定包括下标 i) ！ 否则无法递推！
2. 确定递推公式：取 断/不断 的最大值 max(nums[i], dp[i-1] + nums[i])
   • 如果从 nums[i] 前断开：则包括下标 i 的最⼤连续⼦序列和为 nums[i]
   • 如果不从 nums[i] 断开：则包括下标 i 的最⼤连续⼦序列和为 dp[i-1] + nums[i]
3. 确定遍历顺序和初始化：从前向后，初始化 dp[0] = nums[0]
   • 从递推公式可以看出 dp[i] 由前序元素 dp[i-1] 推出，根本是 dp[0]
   • 根据 dp 数组含义, dp[0] 表示包括下标 0 的最⼤连续⼦序列和，即只包含 nums[0]，所以 dp[0] = nums[0]

class Solution:def maxSubArray(self, nums: List[int]) -> int:dp = [0 for _ in range(len(nums))]  ## dp[i] 表示包括下标 i 的最⼤连续⼦序列和dp[0] = nums[0]  ## 初始化：dp[0] = nums[0]for i in range(1, len(nums)):dp[i] = max(nums[i], dp[i-1]+nums[i])  ## 递推公式return max(dp)