Sunday面试指南

最大子数组和怎么求?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本轮选择
333首元素
-213接上前段
455接上前段
-7-25接上前段
555从5重开

走到-7时,end成为负数,best仍是5。下一轮5不再带上这个负担。这个例子也说明,当前结尾最优和全局最优,不必指向同一段。

end和best,记的是不同答案

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

浏览公司面试真题 →
简历汪永久免费在线制作简历,模板直接套用、导出无水印,永久免费、下载免费,不需要付费解锁任何功能。去写简历