这道题我见过太多次了无论在笔试还是面试里它出现的频率都高得吓人。不夸张地说它几乎是动态规划入门第一课级别的存在——题目本身看起来很简单一个整型数组找出一段连续的子数组让和最大。像题目里给的例子{-2, 5, 3, -6, 4, -8, 6}一眼扫过去就知道答案是5 3 8也就是下标 1 和下标 2 两个元素相加。但真到了实现环节很多人的第一反应还是三层循环暴力求解然后被问到能不能优化的时候卡住。这篇东西我打算把从暴力到 Kadane 算法的完整推导过程写清楚把每一步为什么这么做、边界在哪里、面试官会怎么追问都摊开来讲。不管你是刚学算法的萌新还是准备跳槽要刷题的老手看完应该都会有点收获。1. 先搞清楚题目在问什么1.1 子数组的定义和题目的隐含条件这道题最容易被忽略的地方是子数组这个词的准确定义。子数组指的是原数组中连续的一段下标必须是紧挨着的。比如在{-2, 5, 3, -6, 4, -8, 6}里面{5, 3}是一个子数组{5, 3, -6, 4}也是一个子数组但{5, -6, 6}就不是——因为这里的元素在原数组里并没有连续出现。这个定义直接决定了后面所有解法的形态。很多人一做题就想着从数组里挑几个数那变成了另一个经典问题——最大子序列和可以跳着选两个问题解法完全不同别搞混。还有一个隐含条件题目说的是整型数组意味着元素可能是正数、负数、零也可能全是负数。这个看似废话的细节恰恰是后面很多坑的源头。初始化答案的时候如果拍脑袋设成 0遇到全负数组就会直接翻车这个我在第 5 部分会专门展开。1.2 为什么暴力解法反而是一个好的起点我见过不少学习者上来就直奔最优解看完 Kadane 算法的代码觉得哇好简单然后就过了。但真到了面试现场面试官往往先问你第一反应是怎么想的而不是请直接默写最优解。暴力的思路其实非常朴素把所有可能的子数组都枚举一遍每个子数组求个和再找出最大值。这个思路天然正确没有任何推导成本而且代码写出来非常符合人类的直觉。哪怕是在真刀真枪的工程场景里如果数组规模不大比如长度在几十到几百暴力的性能也完全可以接受。所以我一直建议碰到这类问题先写暴力哪怕只是用来验证后续优化版本的正确性也值得做。暴力解的核心是枚举起点和终点。可以用两重循环枚举i是起点j是终点然后从i到j累加求和。这么写是三层循环时间复杂度 O(n³)。稍微优化一下在枚举终点的过程中顺便累加把第三层循环省掉就变成了 O(n²)。这个优化过程本身就是一道很经典的如何降低一个数量级复杂度的练习题。// 暴力解法时间复杂度 O(n^2) int maxSubarraySum(int a[], int n) { int maxSum a[0]; // 注意这里不能初始化为 0 for (int i 0; i n; i) { int currentSum 0; for (int j i; j n; j) { currentSum a[j]; if (currentSum maxSum) { maxSum currentSum; } } } return maxSum; }这段代码的关键点在于maxSum的初始值。如果数组全为负数初始化为 0 的话最大值会被错误地算成 0因为任何一个负数都比 0 小。所以这里初始化为a[0]数组第一个元素是最稳妥的。当然如果你确定数组里一定有正数初始化为 0 也能过但写代码的原则是处理所有边界情况而不是赌输入数据。2. 从暴力到一步到位的优化链条2.1 暴力解法的瓶颈在哪里O(n²) 的解法在数组长度为 10^3 时还能跑大约十万次操作到了 10^5 量级就是 10^10 次操作现代 CPU 每秒大概能执行几十亿次简单运算也就是说要跑好几秒甚至更久。而真实场景中数组长度到达百万量级一点也不夸张这时候就需要一个更聪明的办法。暴力的本质是枚举所有起点和终点。但仔细想想对于每一个位置我们根本不关心以它为终点的所有子数组我们只关心以它为终点的子数组中和最大的那一个。一旦有了这个视角问题就从一个枚举问题变成了一个递推问题。2.2 核心观察以 i 结尾的最大子数组和关键洞察只有一句话以第 i 个元素结尾的所有子数组要么只有第 i 个元素自己要么是以第 i-1 个元素结尾的最大子数组再加上第 i 个元素。为什么因为一个以a[i]结尾的子数组往前延伸时必然覆盖a[i-1]。如果我想让这个子数组的和最大那前面那部分就必须是以a[i-1]结尾的所有子数组中和最大的那个。这是典型的动态规划最优子结构。用数学语言表达就是dp[i] max(dp[i-1] a[i], a[i])其中dp[i]表示以a[i]结尾的子数组的最大和。这个递推式就是 Kadane 算法最大子数组和算法的核心。它的直观含义是如果前面那段子数组加上当前元素之后比当前元素单独还小说明前面的子数组是累赘不如从当前元素重新开始。这就像爬山如果前面积累的高度加上当前位置还不如原地起步高那不如放弃前面的路从这里重新出发。2.3 用题目中的数据走一遍完整推导纸上谈兵没有意义我们真刀真枪地用手算一算题目里的数组{-2, 5, 3, -6, 4, -8, 6}。下标 ia[i]dp[i-1] a[i]a[i]dp[i]当前全局最大值0-2不存在-2-2-215-2 5 3555235 3 83883-68 (-6) 2-628442 4 64685-86 (-8) -2-8-2866-2 6 4668看这张表有几个点值得注意。下标 1 的时候dp[0] a[1] -2 5 3小于a[1] 5所以dp[1]选择从 5 重新开始。为什么因为前面的-2对以 5 结尾的子数组来说是一个拖后腿的存在抛弃它更划算。下标 2 的时候dp[1] a[2] 5 3 8大于3所以延续前面的子数组{5, 3}得到最大值 8。下标 3 加了一个-6dp[3]降到了 2但这不影响全局最大值 8因为全局最大值记录的是历史上出现过的最大dp值不是当前dp值。很多初学者在实现时犯的错误就是只维护dp[i]而忘了维护历史最大值导致输出的是以最后一个元素结尾的子数组的最大和而不是全数组的答案。下标 6 是另一个容易困惑的地方dp[5] 6 -2 6 4小于6所以重新开始。这里说明一个事实dp[i]并不一定是单调递增或递减的它只关心以当前位置结尾的最大和而这个最大和可以被一个很大的负数打断然后重新起头。2.4 空间优化的魔法为什么只需要两个变量看递推式dp[i] max(dp[i-1] a[i], a[i])你会发现一个关键事实计算dp[i]只需要dp[i-1]再往前的信息完全用不上。这意味着我们根本不需要一个数组来存所有dp值只要两个变量滚动着用就行currentSum当前这个位置的dp[i]maxSum到目前为止出现过的最大值这就是 Kadane 算法的最终形态时间复杂度 O(n)空间复杂度 O(1)。从 O(n²) 降到 O(n) 只靠一个递推思路的转变这就是动态规划的魅力所在——不需要花哨的技巧只需要抓住问题结构中的最优子结构。3. 三种语言的 Kadane 算法落地与细节处理3.1 C 语言实现与边界情况用 C 语言实现 Kadane 算法需要特别注意指针和数组长度的传参。这里给出一个能直接跑起来的完整函数int maxSubArray(int* nums, int numsSize) { if (numsSize 0) { // 根据题目约定处理空数组这里抛个标志或者直接返回 0 return 0; } int currentSum nums[0]; int maxSum nums[0]; for (int i 1; i numsSize; i) { // 核心递推要么延续之前的子数组要么从当前元素重新开始 if (currentSum nums[i] nums[i]) { currentSum currentSum nums[i]; } else { currentSum nums[i]; } if (currentSum maxSum) { maxSum currentSum; } } return maxSum; }这里的if-else其实就是max函数的展开写法。有些编译器对max支持不好或者面试时不想引额外的库函数手写if更稳妥。另外注意循环从i 1开始因为i 0的情况已经在初始化时处理掉了否则会重复计算一次a[0]。3.2 Python 实现与可读性优化Python 的写法可以非常简洁但简洁不代表难以理解。我通常先写一个教学版再写一个精简版面试时先讲教学版再展示如何压缩。def max_subarray_sum(nums): # 教学版思路直白适合面试讲解 if not nums: return 0 current_sum nums[0] max_sum nums[0] for num in nums[1:]: # 核心递推式dp[i] max(dp[i-1] a[i], a[i]) current_sum max(current_sum num, num) max_sum max(max_sum, current_sum) return max_sumPython 的max函数内置写起来非常顺手。但有个细节nums[1:]会创建新的切片如果数组很大这个切片会额外占用内存。严格来说这不太符合 O(1) 空间的精神。用for i in range(1, len(nums))可以避免切片但代码稍微啰嗦一点。在大数据量的场景下我建议用range版本虽然切片在现代 Python 中不一定真的复制取决于具体实现但养成不浪费内存的习惯总没错。3.3 Java 实现与数组下标陷阱Java 的写法介于 C 和 Python 之间需要显式指定数组下标正好可以展示一个容易踩坑的地方public int maxSubArray(int[] nums) { if (nums.length 0) { return 0; } int currentSum nums[0]; int maxSum 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; }一个常见的错误是写for (int i 0; i nums.length; i)然后currentSum Math.max(nums[i], currentSum nums[i])。这样写问题不大因为i0时算出来还是nums[0]但有些同学会把maxSum也放进循环里初始化导致maxSum被覆盖两次。代码逻辑上没问题但读起来绕。更关键的是数组为空的判断必须放在最前面否则nums[0]会抛数组越界异常。3.4 四种典型测试用例与结果验证写完代码不能只看题目给的例子就跑要主动构造边界情况。我每次都会用下面这几组数据来验证测试用例数组期望输出原因常规混合{-2, 5, 3, -6, 4, -8, 6}8题目原例全负数{-3, -5, -2, -7}-2不能返回 0全正数{1, 2, 3, 4}10所有元素加起来单个元素{7}7最小规模零元素{0, -1, 0, 3}3零不改变和但也不能把 0 当最大值特别是全负数这个用例最能检验maxSum初始值是否写对了。如果初始化成 0全负数组会错误地返回 0。这也是我在 1.2 节强调初始化为a[0]的原因。4. 分治解法另一种拆解问题的思路4.1 分治的核心逻辑答案藏在哪里动态规划的思路是顺着数组尾部延伸而分治的思路是把数组一刀切成两半。对于一个数组a[l..r]它的最大子数组和只可能有三种情况完全在左半边a[l..mid]里完全在右半边a[mid1..r]里跨越中点左半边选一部分右半边选一部分拼成一个完整的子数组前两种情况是递归的子问题直接调用自身就能解决。第三种情况需要单独处理从左半边最右边往左延伸找到一个以 mid 结尾的最大后缀和从右半边最左边往右延伸找到一个以 mid1 开头的最大前缀和两段加起来就是跨中点的最大子数组和。为什么第三种情况要这么算因为只要一个子数组跨越了中点它一定包含a[mid]和a[mid1]。从这两个位置分别往两端延伸延伸的原则是只看这段的和够不够大不用管整段是否最优——跨越中点的子数组被拆成两半每一半独立最优合起来就是整体最优。这背后的思想和动态规划是一致的全局最优来自局部最优的组合。4.2 分治代码实现与复杂度分析int maxCrossingSum(int a[], int left, int mid, int right) { // 左半边从 mid 往左累加找最大后缀和 int leftSum a[mid]; int leftMax a[mid]; for (int i mid - 1; i left; i--) { leftSum a[i]; if (leftSum leftMax) { leftMax leftSum; } } // 右半边从 mid1 往右累加找最大前缀和 int rightSum a[mid 1]; int rightMax a[mid 1]; for (int i mid 2; i right; i) { rightSum a[i]; if (rightSum rightMax) { rightMax rightSum; } } return leftMax rightMax; // 跨中点的最大子数组和 } int maxSubarraySumDivide(int a[], int left, int right) { if (left right) { return a[left]; // 只有一个元素它就是答案 } int mid left (right - left) / 2; int leftMax maxSubarraySumDivide(a, left, mid); int rightMax maxSubarraySumDivide(a, mid 1, right); int crossMax maxCrossingSum(a, left, mid, right); // 三者取最大 if (leftMax rightMax leftMax crossMax) { return leftMax; } else if (rightMax leftMax rightMax crossMax) { return rightMax; } else { return crossMax; } }时间复杂度是 O(n log n)因为每层递归都要做一次 O(n) 的跨越计算递归深度是 log n 层。空间复杂度是 O(log n)对应递归栈的深度。虽然整体不如 Kadane 算法的 O(n)但这个思路在很多扩展问题里很有用比如无法用动态规划直接建模的场景或者需要最大子数组在哪个区间这种额外信息时分治的递归结构反而更方便。分治代码里最容易写错的地方有两个。第一个是mid的计算写成(left right) / 2在left和right都很大时可能整数溢出写成left (right - left) / 2才是安全的。第二个是maxCrossingSum里左半边的初始值有人习惯把leftMax初始化为一个极小数比如INT_MIN但如果数组只有一个元素a[mid]本身就是那个值直接初始化成a[mid]更不容易出错。4.3 分治和动态规划的对比什么时候用哪个这两者不是竞争关系而是互补关系。动态规划重在看递推结构适合能写出状态转移方程的题目分治重在看如何切分适合能自然分成互不相交的几块、且合并逻辑清晰的题目。对于最大子数组和这个问题动态规划更快、代码更短是面试中应该优先给出的解法。但如果你能同时讲出分治版本并且说清楚两者的复杂度差异和各自的适用场景面试官通常会眼前一亮——这说明你不只是背了一个算法模板而是真的理解问题的结构。我见过不少候选人Kadane 倒背如流但一问到分治就卡壳这种只会一种解法的情况在深度面试里是非常吃亏的。5. 进阶变种与面试官最爱的追问方向5.1 不只是求和如何把最大子数组本身找出来原始问题只要求和但很多场景下我们需要的是哪一段子数组达到这个最大值。比如在做股票数据分析时你不仅想知道最大收益还想知道该买入和卖出的日期点。实现方式很简单在 Kadane 算法的基础上每当currentSum重新开始即currentSum nums[i]就把start临时标记为i每当maxSum被更新就同步记录end i和bestStart start。这样遍历结束后bestStart到end就是最优子数组的下标区间。int maxSubArrayWithRange(int a[], int n, int* bestStart, int* bestEnd) { int currentSum a[0]; int maxSum a[0]; int start 0; *bestStart 0; *bestEnd 0; for (int i 1; i n; i) { if (a[i] currentSum a[i]) { // 条件等价于 currentSum 0说明前面的子数组是累赘 currentSum a[i]; start i; } else { currentSum currentSum a[i]; } if (currentSum maxSum) { maxSum currentSum; *bestStart start; *bestEnd i; } } return maxSum; }注意这里判断条件我换了个写法a[i] currentSum a[i]等价于currentSum 0。这意味着什么只要前面累加的和是负数它就是一个负资产应该果断止损。这跟生活中的投资逻辑一模一样一个持续亏损的仓位该斩仓就斩仓不要为了已经投入的成本继续往里搭钱。5.2 环形数组变种打破线性思维面试官最喜欢的变种之一是允许子数组跨越数组末尾和开头形成环形求环形数组的最大子数组和。比如{5, -3, 5}这个数组线性最大子数组和是 75 (-3) 5不对线性最大是 5 或 5但环形的答案是 10取两个 5。这个变种的核心 trick 是环形最大子数组和等于数组总和减去最小子数组和。为什么因为在一个环上你选了一段作为答案那么剩下的那段一定是最小子数组。换个角度想把环形问题转换成要么直接用线性最大子数组和跨过首尾的那段不如线性直接选的、要么用总和减去线性最小子数组和剔除掉一段负数。实现上只需要把 Kadane 算法改成同时维护最大值和最小值int maxSubarraySumCircular(int a[], int n) { int totalSum 0; int currentMax 0; int maxSum INT_MIN; int currentMin 0; int minSum INT_MAX; for (int i 0; i n; i) { totalSum a[i]; currentMax (currentMax a[i] a[i]) ? (currentMax a[i]) : a[i]; maxSum (maxSum currentMax) ? maxSum : currentMax; currentMin (currentMin a[i] a[i]) ? (currentMin a[i]) : a[i]; minSum (minSum currentMin) ? minSum : currentMin; } if (maxSum 0) { return maxSum; // 全负数组环形也不会更好直接返回最大值 } return (totalSum - minSum maxSum) ? (totalSum - minSum) : maxSum; }这里有个隐蔽的边界如果数组全部为负数totalSum - minSum会等于 0反而比正确的负数最大值还大。所以必须先判断maxSum是否小于 0如果是就直接返回。这个细节我在真实面试里见过很多人写漏属于典型的看似简单实则暗藏杀机的问题。5.3 二维矩阵的最大子矩阵和另一位高频变种是二维问题给定一个m x n的矩阵找一个子矩阵使元素之和最大。解决办法是把二维问题转成一维问题枚举子矩阵的上边界top和下边界bottom然后把每一列在这个区间内的元素之和算出来得到一个一维数组对这个一维数组跑 Kadane 算法。int maxSubmatrixSum(int** matrix, int m, int n) { int maxSum INT_MIN; for (int top 0; top m; top) { int colSum[n]; memset(colSum, 0, sizeof(colSum)); for (int bottom top; bottom m; bottom) { for (int col 0; col n; col) { colSum[col] matrix[bottom][col]; } // 对 colSum 跑 Kadane int current colSum[0]; int best colSum[0]; for (int col 1; col n; col) { current (current colSum[col] colSum[col]) ? (current colSum[col]) : colSum[col]; best (best current) ? best : current; } if (best maxSum) { maxSum best; } } } return maxSum; }复杂度是 O(m² · n)在一维 O(n) 的基础上增加了一个枚举上下边界的 O(m²) 循环。这个变种的价值在于它展示了一个很重要的算法思维模式把高维问题通过压缩降成一维问题。很多看起来复杂的题目本质上都能拆解成若干轮已知问题。5.4 面试现场Kadane 之后的连环追问如果你在面试中写出了 Kadane 算法面试官通常不会直接让你走而是会顺着往下追问如果允许你重新排列数组中的元素最大子数组和怎么求——这个问题的答案是把所有正数加起来就完了因为你可以任意排列正数就能连在一起。如果要求子数组长度至少为 k怎么做——这就需要维护一个长度为 k 的滑动窗口或者用前缀和加滑动窗口的最小值来求解。如果数组很长但只允许遍历一次而且不允许用额外空间能做吗——这其实就是在引导你给出 Kadane 算法因为它天然就是一遍扫描加 O(1) 空间。如果数组里有大量的值比如上亿个元素怎么在分布式环境里算——这会把问题导向分治思想每个节点算局部最大前缀和、最大后缀和、最大子数组和然后在合并节点组合这些信息。这些追问看起来五花八门背后其实都在考察你有没有真正理解最大子数组和这个问题的数据结构特征前缀、后缀、连续段。与其背一堆答案不如从原理上吃透递推式dp[i] max(dp[i-1] a[i], a[i])和分治的三种情况追问再怎么变也离不开这些基础。6. 常见问题与踩坑实录那些年我犯过的错6.1 maxSum 初始化成 0全负数组直接翻车这个坑我在初学阶段踩过在面试别人的时候也见无数人踩过。很多人看题目里数组有正数就理所当然地把答案初始化为 0结果一到全负数组就输出 0而正确答案应该是最大的那个负数比如{-3, -5, -2}应该返回 -2。解决方式前面已经说过初始化为a[0]或者用INT_MIN。但用INT_MIN有一个麻烦如果数组长度是 0你会返回一个莫名其妙的大负数。所以在处理空数组时需要约定好返回什么通常是 0 或者抛异常。在刷题平台上题目一般保证数组非空但工程实践中必须考虑空数组的情况。6.2 只维护 dp 数组、忘记全局最大值我见过一种半吊子的实现正确算出了dp[i]但最后直接返回dp[n-1]而不是max(dp[0..n-1])。这在数组单调递增时碰巧是对的因为dp[i]一直在涨最后一个就是最大的。但回到题目给的例子最后一个dp值是 6而全局最大值是 8直接返回就错了。这个错误的根源是dp[i]的定义是以 i 结尾的最大和而题目要的是所有子数组的最大和。两者不一定相等。所以maxSum这个变量是必须的它不是优化而是语义本身。6.3 整数溢出当 sum 超过 int 范围题目里只说整型数组没说整数范围。在实际工程中一个包含 10^6 个元素的 int 数组如果每个元素都接近 2^31 - 1子数组和会远远超过 int 的范围。在 C/C/Java 中这意味着有符号整型溢出行为是未定义的C/C或者回绕Java。处理方式有几种明确题目的约束范围把累加变量声明为long或long long或者在实际计算前预判是否会溢出。在面试中这个问题不常考但在真实的数据处理场景里我踩过一次明明算法逻辑没问题结果却诡异的 bug最后排查半天发现是 int 溢出从那以后我在做累加题时都习惯性用更大的类型这是很多老开发都有的肌肉记忆。6.4 递归分治的栈溢出隐患分治解法的递归深度是log n理论上不会栈溢出但如果递归函数写得有问题比如mid计算不对导致无限递归那就另当别论了。我在实现时习惯在递归函数开头加一个if (left right)的防御性判断虽然正常路径永远走不到但真出了 bug 时能更快定位。还有一个分治特有的坑maxCrossingSum里如果数组只有两个元素mid和mid1都要存在下标的边界要想清楚。我建议写完后无聊时拿{1, 2}、{1, 2, 3}、{-1, -2, -3}各跑一遍确保没有越界。6.5 动手总结一份自测清单我每次写完一个算法题都不会急着提交而是会按下面的清单自查一遍数组全为正数答案应该是所有元素之和数组全为负数答案应该是最大那个负数数组有正有负但最大子数组恰好在开头或末尾单个元素的数组两个元素的数组最大子数组跨越数组中间位置随机数据和暴力解法对拍验证这个在本地写一小段脚本对拍几百组随机数据能发现大多数隐藏 bug对拍是性价比最高的测试方法写一个简单但绝对正确的暴力版本再写一个优化版本然后用随机输入不断对比两者输出。只要有一次不一致就说明优化版本有 bug。这个方法我已经用了很多年几乎成了所有算法实现的标配步骤。第 1 节里我提到的先写暴力这时候就派上用场了——它不仅仅是思路的起点更是验证最优解的标尺。回到最初那个问题{-2, 5, 3, -6, 4, -8, 6}的最大子数组和为什么是 8因为5 3这一段和最大后面-6 4把和拉低到 6再后面的-8直接让累加归负最后的 6 只能单独重新开始。Kadane 算法正是沿着这个何时止损、何时重新开始的思路一遍扫描就能找到答案。如果你刚开始学算法我建议你亲手把这张 dp 表画几遍再写三遍代码暴力版、分治版、Kadane 版。每一版都会加深你对这个问题结构的理解。等你把这道题吃透了再去看股票最大收益问题、最长连续递增序列、二维最大子矩阵和这些变种会发现它们的底子其实是同一个东西。算法学习的乐趣就在于此一道经典题就是一把打开一类问题的钥匙。