最大子数组和怎么求?Kadane 算法为什么只需要遍历一次?
下面是模拟面试对话,用来讲解本题,不是真实面经。
🧑💻 面试官:最大子数组和怎么求?
🙋♂️ 我:遍历求和,遇到负数就重新开始。
🧑💻 面试官:数组里有负数,最优答案一定不能包含它吗?
🙋♂️ 我:可能还能把两边的正数连起来。
🧑💻 面试官:那重新开始的依据到底是什么?如果数组全是负数,初始化为0会得到什么?
决定是否接续,要看前面这段累计和值不值得带上,不能只看当前数字是不是负数。
面试速答(60 秒版)
最大子数组要求连续,且这里至少选一个元素。Kadane算法保存两个值:以当前位置结尾的最大和,以及截至目前的全局最大和。
走到当前数字时,只有两种选择。继续接在前一段后面,或者从当前数字重新开始。因此当前状态是 max(当前值, 前一状态 + 当前值),再用它更新全局答案。
前一段的和为负,带上它只会让当前结果更小,才值得丢掉;不能看到一个负数就断开。
两个状态都从首元素初始化,这样全负数也能选到最大的那个负数。每个元素只处理一次,时间是O(n),只求最大和时额外空间是O(1)。

知识点详解:先定义结尾位置,才能只保留一个状态
连续区间,不允许跳过中间的负数
假设数组是 [3, -2, 4]。可以选整段得到5,却不能跳过-2把3和4直接相加成7,那已经变成另一类选择问题。
一个负数也不一定要丢。它可能连接两段更大的收益。更有用的问题是,走到4时,前面连续到-2的那段收益还值得保留吗?
这就把“遍历所有起点和终点”,转成了对当前位置的判断。

end只回答必须在这里结束的最大和
走到位置i,合法答案如果必须在这里结束,要么只有当前元素,要么把前面以i-1结束的一段接上当前元素。所有更差的前段,接同一个当前元素后仍更差,因此只需要保留前段最优值。
于是 end = max(x, end + x)。而最佳区间也可能早已结束,所以再用 best = max(best, end) 保存全局结果。
两个变量不能混用。如果把历史best直接接上当前数字,中间可能跳过一些元素,连续条件就丢了。
用一张小表,看两种状态如何变化
以 [3, -2, 4, -7, 5] 为例。
| 当前值 | 以这里结尾的end | 历史best | 本轮选择 |
|---|---|---|---|
| 3 | 3 | 3 | 首元素 |
| -2 | 1 | 3 | 接上前段 |
| 4 | 5 | 5 | 接上前段 |
| -7 | -2 | 5 | 接上前段 |
| 5 | 5 | 5 | 从5重开 |
走到-7时,end成为负数,best仍是5。下一轮5不再带上这个负担。这个例子也说明,当前结尾最优和全局最优,不必指向同一段。

TS与Python实现,先处理空输入
原题保证非空,下面额外明确拒绝空数组。TS示例假设所有求和都在安全整数范围内,生产输入需要相应校验。
TypeScript
function maxSubarray(nums: number[]): number {
if (nums.length === 0) throw new Error('数组不能为空');
let end = nums[0];
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
end = Math.max(nums[i], end + nums[i]);
best = Math.max(best, end);
}
return best;
}
Python
def max_subarray(nums):
if not nums:
raise ValueError('数组不能为空')
end = best = nums[0]
for i in range(1, len(nums)):
end = max(nums[i], end + nums[i])
best = max(best, end)
return best
Python没有为了遍历写 nums[1:],避免无意复制额外数组。两版都保留常数额外状态。
需要答案区间,就同步记录起点
只返回和时,两变量足够。如果要返回左右端点,就记录当前end对应的起点;从当前元素重开时更新它,best变大时保存整段端点。
同和时还要约定要哪一段,是最早、最短,还是任意一段。上面代码只返回数值,没有假装处理所有端点规则。
测试不能只用有大量正数的例子。[-5,-2,-9]应返回-2;[0]返回0,空输入按这里的接口约定报错。还可以穷举短数组,对照所有非空连续区间的暴力答案。

技术依据:LeetCode 53 题意。工程场景与解法按本文说明的条件展开。
面试官继续追问
为什么这是动态规划,也能叫贪心?
状态转移是动态规划表达;丢掉负前缀的判断也有贪心解释。关键是证明保留前段最优足够,而不是争名称。
前段为0时必须重开吗?
只求和,两种选择相同;若要端点,则取决于同和时的区间规则。
面试速记卡
- 限制:必须连续,至少选一个元素。
- 状态:end必须在当前位置结束,best保存历史最优。
- 转移:当前值与end加当前值之间取最大。
- 初始化:使用首元素,全负数不能默认返回0。
- 复杂度:O(n)时间,求和版O(1)额外空间。
公司面试真题
真题根据求职者公开面经整理,题意经过概括,非逐字原话或公司官方题库;本文为 Sunday 的独立解析。
字节跳动 · 风控算法 · 原帖未明确批次
怎样求最大连续子数组和?(题意整理)
字节风控算法面经 ↗
原帖发布于 2025-09-21