53. 最大子数组和（Maximum Subarray）

频次 ★★★★★ · 难度 🟢 · 高频：全厂

题目

给定一个整数数组 nums，找到一个具有最大和的连续子数组（至少包含一个元素），返回其最大和。

示例：

输入: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大为 6

思路

Kadane 算法：

• 遍历数组，维护当前连续子数组和 currentSum
• 如果 currentSum < 0，说明前面的和对后续是拖累，从当前元素重新开始
• 用 maxSum 记录历史最大值

核心思想：负的累加和只会拖累后面的子数组，所以一旦变成负数就舍弃。

代码

public int maxSubArray(int[] nums) {
    int maxSum = nums[0], currentSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

复杂度

• 时间：O(n) — 一次遍历
• 空间：O(1) — 两个变量

边界条件

• 数组只有一个元素：maxSum = currentSum = nums[0]，循环不执行，直接返回该元素本身。
• 全为负数（如 [-3,-1,-2]）：算法仍然正确，返回其中最大的单个元素（-1），因为题目要求”至少包含一个元素”，不能返回空子数组对应的 0。
• 全为正数：等价于整个数组求和，currentSum 永远不会因为 < 0 而重置。

变式

• 要求返回具体的子数组（不只是和）：额外维护子数组起始下标，当 currentSum 被重置为 nums[i] 时更新起始下标，当 maxSum 被刷新时记录当前的起止下标。
• 环形数组的最大子数组和（LeetCode 918 题）：分两种情况讨论——最大子数组不跨越首尾（直接 Kadane）或跨越首尾（等价于总和减去最小子数组和），取两者较大值。
• 152. 乘积最大子数组：把”和”换成”积”后，负负得正的特性使得单变量不够用，需要同时维护最大值和最小值。

易错点

• 容易把”至少包含一个元素”的约束忽略掉，写成”如果全是负数就返回 0”，这是错误的——必须真的选出一个子数组。
• currentSum = Math.max(nums[i], currentSum + nums[i]) 这一步的含义是”要不要抛弃之前的累积重新开始”，不是简单的”只要变负就清零再加当前值”，两者在数学上等价但后一种写法容易在下标处理上出错。

面试追问

• Kadane 算法的本质是什么，为什么正确？ 它是一种简化的动态规划：dp[i] 表示”以第 i 个元素结尾的最大子数组和”，状态转移是 dp[i] = max(nums[i], dp[i-1] + nums[i])，因为只依赖前一个状态，可以用一个变量滚动更新，这也是很多”O(1) 空间 DP”题目的通用套路。
• 能不能用分治法做？ 可以，把数组从中间分成两半，最大子数组要么完全在左半部分，要么完全在右半部分，要么跨越中点（这部分需要从中点向两边分别扩展求最大前缀/后缀和），复杂度是 O(n log n)，比 Kadane 慢，一般作为”还有没有别的思路”的追问答案，而不是首选解法。

关联题

• 同套路：152. 乘积最大子数组 —— Kadane 的乘法变体
• 进阶：121. 买卖股票的最佳时机 —— 对差价数组跑 Kadane 就是本题；918. 环形子数组的最大和
• 易混：560. 和为 K 的子数组 —— 求计数不求最值，套前缀和哈希
• 知识点：动态规划专题见动态规划