最大子数组和
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1
示例 2
示例 3
模拟答题者思考
1. 最直接：枚举所有连续子数组 [l..r]，对每个区间求和取最大，双重循环 O(n²)，n=10⁵ 会超时。
2. 重复在哪里？固定右端点 r 时，左端点 l 从 0 到 r 的区间和 sum(l,r) 可以从前一个 sum(l,r-1) 加上 nums[r] 得到——但更简单的是只关心「以 r 结尾」的最优子数组。
3. 子问题定义：设 dp[i] = 以 nums[i] 结尾的连续子数组的最大和。则 dp[i] = max(nums[i], dp[i-1] + nums[i])——要么单独成段，要么接在前一段后面。
4. 全局答案不在 dp[n-1]，而是 max(dp[0..n-1])：最优子数组可能结束在任意位置（如样例中结束在下标 6 而非末尾）。
5. 手推 [-2,1,-3,4,-1,2,1,-5,4]：cur 依次为 -2→1→-2→4→3→5→6→1→5，ans 在扫到 6 时取到最大值 6，对应子数组 [4,-1,2,1]。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
cur | int | 定义：以当前下标 i 结尾 的连续子数组的最大和维护：每扫到一个新元素，要么「接上前面的子数组」，要么「从当前元素重新开始」——取两者较大值 更新： cur = max(nums[i], cur + nums[i])，即 Kadane 核心递推 |
ans | int | 定义：遍历过程中见过的所有「以某位置结尾的子数组」中的全局最大和 维护：每更新一次 cur，同步 ans = max(ans, cur)更新：初始 ans = nums[0]（至少含一个元素），扫完返回 ans |
i | int | 定义：从左到右扫描的下标，代表「当前考察的结尾位置」 维护： for i in range(1, n)，第 0 个元素已用于初始化 cur 和 ans更新：每轮用 nums[i] 更新 cur，再刷新 ans |
落码步骤
1. 初始化 cur = ans = nums[0]（子数组至少含一个元素）
2. 从下标 1 遍历到 n-1
3. 对每个 nums[i]：cur = max(nums[i], cur + nums[i])（接上 or 重启）
4. 更新全局：ans = max(ans, cur)
5. 返回 ans
代码实现
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
cur = ans = nums[0]
for i in range(1, len(nums)):
cur = max(nums[i], cur + nums[i])
ans = max(ans, cur)
return ansclass Solution {
public:
int maxSubArray(vector<int>& nums) {
int cur = nums[0], ans = nums[0];
for (int i = 1; i < nums.size(); i++) {
cur = max(nums[i], cur + nums[i]);
ans = max(ans, cur);
}
return ans;
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
答案不是 dp[n-1]：最大子数组可以结束在任意位置，必须全程维护 ans = max(ans, cur)，不能只返回最后一次的 cur。
全负数数组：如 [-3,-2,-1]，cur 会不断被 max(nums[i], ...) 重置为当前元素，ans 应取最大的那个负数（-1），不能返回 0。
初始化勿用 cur=0：子数组至少包含一个元素，应从 nums[0] 开始；若 cur 初值为 0，全正数组虽能蒙对，全负时会错成 0。
必测边界 Case
nums = [1] → 1（唯一子数组即自身）
nums = [-3, -2, -1] → -1（必须选一个元素，取最大负数）
nums = [5, 4, -1, 7, 8] → 23（整个数组即最优，无需截断）
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6（最优子数组不贴首尾）
nums = [-1, -2, 5, -1, 3] → 7（前面负前缀应被丢弃，从 5 重启）