LeetCode 53. 最大子数组和是一道经典的动态规划题目。核心思路是贪心/动态规划在遍历数组时我们需要决定当前元素是“加入前面的子数组”还是“自己另起炉灶”。下面为你提供两种 Python3 的实现方式解法一标准动态规划最直观维护一个 dp 数组dp[i] 表示以 nums[i] 结尾的最大子数组和。class Solution:def maxSubArray(self, nums: list[int]) - int:# dp[i] 表示以 nums[i] 结尾的最大子数组和dp [0] * len(nums)dp[0] nums[0]max_sum dp[0] for i in range(1, len(nums)): # 状态转移方程要么和前面的子数组连起来要么自己重新开始 dp[i] max(nums[i], dp[i - 1] nums[i]) # 更新全局最大值 max_sum max(max_sum, dp[i]) return max_sum解法二空间优化推荐贪心思想因为 dp[i] 只依赖于 dp[i-1]所以我们只需要一个变量 current_sum 来记录当前的累加和即可将空间复杂度降到 O(1)。class Solution:def maxSubArray(self, nums: list[int]) - int:current_sum nums[0]max_sum nums[0]for i in range(1, len(nums)): # 如果前面的累加和是负数不如直接从当前元素重新开始 current_sum max(nums[i], current_sum nums[i]) # 记录遍历过程中的最大值 max_sum max(max_sum, current_sum) return max_sum 核心要点解析核心逻辑状态转移这道题的精髓在于 current_sum max(nums[i], current_sum nums[i])。如果 current_sum nums[i] nums[i]说明前面的累加和是正数对当前元素有增益继续累加。如果 current_sum nums[i] nums[i]说明前面的累加和是负数拖了后腿果断抛弃前面的结果从 nums[i] 重新开始。全局最大值注意 current_sum 只是“以当前元素结尾”的最大和而题目要求的是整个数组中的最大子数组和所以必须用一个 max_sum 变量在每次迭代时记录历史最大值。复杂度分析时间复杂度O(n)只需遍历一次数组。空间复杂度O(1)解法二仅使用了常数级别的额外空间。如果你刚做完这道题强烈建议紧接着做 LeetCode 152. 乘积最大子数组。它的思路几乎一样但因为负负得正需要同时维护“当前最大值”和“当前最小值”是对这道题思维的绝佳拓展