最大子数组和
Maximum Subarray
本机进度仅保存在当前浏览器
题目描述
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]，连续子数组 [4, -1, 2, 1] 的和最大，输出 6。
解题思路
- 状态定义：dp[i] 为「以 nums[i] 结尾」的最大子数组和——必须强制包含 nums[i]，保证状态连续推进。
- 转移：前面的累计是资产还是负资产？dp[i] = max(dp[i-1] + nums[i], nums[i])，即负贡献直接舍弃重启。
- 答案为所有 dp[i] 的最大值；用单变量滚动即可，空间 O(1)，这就是 Kadane 算法。
参考实现
查看参考实现Python · 建议先自行作答
def maxSubArray(nums):
# cur 为以当前元素结尾的最大和，负贡献则重启
cur = best = nums[0]
for x in nums[1:]:
cur = max(cur + x, x)
best = max(best, cur)
return best