最大子数组和与Kadane算法：从动态规划到面试变体全解析

1. 为什么一道简单题能成为热题100的钉子户如果你刷过Leetcode热题100大概率会在这个位置上停留过53. 最大子数组和。题目描述短得令人发指——给你一个整数数组nums找出一个具有最大和的连续子数组返回其最大和。示例是[-2,1,-3,4,-1,2,1,-5,4]输出6对应子数组[4,-1,2,1]。我第一次做这道题的时候内心是有些轻蔑的。求子数组最大和把所有连续子数组枚举出来求和取最大不就行了然后我写了个暴力解一提交在数据规模稍大的用例上直接超时。那一刻我才意识到这道题标签虽然是简单但它考察的是动态规划里最经典的状态定义思维是面试官非常喜欢层层追问的一道题。这道题适合谁准备笔试面试的应届生、跳槽刷题的老兵、学习动态规划但总是卡在状态定义上的初学者以及那些已经能AC但说不清楚为什么dp数组可以被优化成单个变量的人。题目本身的代码量可能不到十行但这十行背后藏着Kadane算法的完整思想还关联着分治、线段树、环形数组、二维矩阵等一串变体。它的核心价值不在于怎么把这道题AC掉而在于搞懂一个问题当遍历到第i个元素时以它作为末尾的最大子数组和到底由谁决定把这个问题想通了动态规划的很多题目都会豁然开朗。这篇文章我会从暴力解开始推演把Kadane算法的推导过程完整走一遍然后再展开分治解法、变体题目以及面试中的追问方向。不讲虚的直接上硬货。2. 暴力解法先明确问题边界再优化2.1 最容易上手的O(n^2)写法暴力解法的思路非常直白枚举每一个可能的子数组起点i和终点j计算nums[i]到nums[j]的累加和用一个变量维护最大值。代码大概是这样的function maxSubArray(nums) { let maxSum -Infinity; const n nums.length; for (let i 0; i n; i) { let currentSum 0; for (let j i; j n; j) { currentSum nums[j]; maxSum Math.max(maxSum, currentSum); } } return maxSum; }注意这里在第二层循环里用了一个currentSum来累积从i到j的和这样单次循环内是O(1)的增量计算整体复杂度是O(n^2)。如果你在第一层循环里写成枚举i和j后再用一层循环求和那就是O(n^3)更没救。O(n^2)解法的正确性完全没有问题但Leetcode上nums的长度可以到10^5量级O(n^2)在最坏情况下需要执行大约10^10次加法运算超时是必然的。这给我们一个很重要的判断当数据规模达到10^5时算法的复杂度必须压到O(nlogn)甚至O(n)。这也是为什么Kadane算法存在的前提。2.2 暴力解暴露出的关键观察写一遍暴力解并不是浪费时间。我在手动模拟暴力过程时发现一个很有价值的细节子数组[4,-1,2,1]能成为最优解是因为它在任何一步累加时都没有把前缀和拖到负数——更准确地说从头开始累加的过程中当前和一旦变成负数它就不可能作为后续更大子数组的有益前缀了。举个例子从-2开始加1当前和变成-1此时如果继续向后加-3只会让和更小。换句话说一个负的前缀累积值只会拖累后面的元素。那不是负的前缀呢比如[4,-1]的当前和是3虽然中间减去1但整体仍然是正收益所以保留4这个起点继续向后扩展是合理的。这个观察正是Kadane算法从O(n^2)优化到O(n)的关键依据我们根本无需枚举起点只需要在遍历过程中维护当前累积和是否值得保留。3. Kadane算法的本质一个状态变量的DP3.1 状态定义是怎么想到的很多人背Kadane算法的时候记住的是一句话遍历数组维护一个当前和如果当前和小于0就重置为当前元素否则累加并不断更新最大值。代码写出来是这样的def maxSubArray(nums): cur_sum 0 max_sum float(-inf) for x in nums: cur_sum max(x, cur_sum x) max_sum max(max_sum, cur_sum) return max_sum这段代码只有四行有效逻辑但问题是为什么cur_sum max(x, cur_sum x)能保证找到全局最大子数组和这需要从动态规划的状态定义讲起。我们定义一个状态dp[i]表示以nums[i]结尾的连续子数组的最大和。注意以nums[i]结尾这个约束条件是整个DP的基石这意味着dp[i]对应的子数组必须包含nums[i]并且它是nums[i]作为最后一个元素的所有子数组中和最大的那一个。那么dp[i]怎么从更小的状态推导出来考虑所有以nums[i]结尾的子数组它们可以分成两类第一类子数组只有nums[i]一个元素和就是nums[i]。第二类子数组长度大于等于2那么它可以被写成以nums[i-1]结尾的某个子数组再加上nums[i]。对于第二类为了让和尽可能大前面的部分当然应该选择dp[i-1]对应的那个最大子数组。所以状态转移方程是dp[i] max(nums[i], dp[i-1] nums[i])这个式子也可以写成dp[i] nums[i] max(0, dp[i-1])意思是如果dp[i-1]是正数就把它接上如果是负数就干脆不要前面那一截从nums[i]重新开始。3.2 为什么dp[i-1]为负数时一定要断开这里有一个很多初学者会疑惑的点如果dp[i-1]是负数直接扔掉那万一后面又出现更大的正数呢扔掉负数前缀会不会错过先苦后甜的机会直接回答不会。因为dp[i]的定义是以nums[i]结尾的最大和而我们最终要求的答案是所有dp[i]中的最大值。如果nums[i]后面还有更大的正数那它对应的状态dp[i1]、dp[i2]在计算时会使用到dp[i]。如果dp[i]本身已经因为包含了一个负前缀而变小了那后面的状态也会跟着变小。举个例子数组[100, -200, 300]。dp[0]100dp[1]max(-200, 100-200)-100dp[2]max(300, -100300)300。最优子数组是[300]不是[100,-200,300]。如果我们在dp[1]处保留负数值-100继续向右扩展得到的是200远不如从300重新开始。所以一旦前缀和变成负数就断掉不是直觉而是严格推导出的结论。这背后其实是最优子结构dp[i]的最优解只取决于dp[i-1]这一个状态满足无后效性——前面的状态一旦确定就不会受未来元素影响。这也是动态规划问题里判断一个状态定义是否有效的重要标准。3.3 空间优化从dp数组到单个变量有了dp数组的定义我们可以写出一个标准的DP版本def maxSubArray(nums): n len(nums) dp [0] * n dp[0] nums[0] ans dp[0] for i in range(1, n): dp[i] max(nums[i], dp[i - 1] nums[i]) ans max(ans, dp[i]) return ans这个版本的时间和空间复杂度都是O(n)。但观察状态转移方程可以发现dp[i]只依赖dp[i-1]不依赖更早的状态所以完全可以用一个curSum变量滚动更新这就得到了Kadane算法的经典四行版本。注意curSum的初始值。很多写法把curSum初始化为0然后每次先curSum max(0, curSum) x这两种写法本质等价但max(x, curSum x)更严谨——它不依赖初始化值的选择。我推荐把cur_sum初始化为0把ans初始化为float(-inf)或nums[0]反正不能初始化为0否则全负数数组会返回错误答案0。4. 回到题目完整推导三种实现与边界细节4.1 从暴力到Kadane的逐步改写过程为了帮助真正想搞懂代码来龙去脉的读者我把改写过程摆出来。先看暴力解for i in range(n): for j in range(i, n): current_sum nums[j] ans max(ans, current_sum)优化的目标是消掉外层循环枚举起点i的那一层。在暴力解里每次重新选择起点icurrent_sum都会被重置。而Kadane的思路是不再显式枚举起点而是通过当前和是否值得保留隐含地维护一个最佳起点。于是内层循环遍历到的每个位置i都成为潜在的结束点而当前和始终保持的是以当前位置为结束点的最大子数组和。这样改写后遍历一遍数组就能得到答案。你可以把cur_sum理解为当前累积的最佳子段和ans理解为历史任何时刻达到的cur_sum的最大值。4.2 输出最大和的同时记录起始和结束下标Leetcode原题只要求返回最大和但面试官如果追问能不能把最大子数组的起始位置也输出你做不出来就尴尬了。其实只要在原代码上增加两个指针start和end。def max_subarray_with_indices(nums): cur_sum 0 max_sum float(-inf) temp_start 0 start 0 end 0 for i, x in enumerate(nums): if cur_sum 0: cur_sum x temp_start i else: cur_sum x if cur_sum max_sum: max_sum cur_sum start temp_start end i return max_sum, nums[start:end1]这里的核心技巧是temp_start与start的分离。每次前缀和变成负数时我们更新temp_start为当前下标表示如果未来要开启一个新的子数组起点可能是这里。但只有真正刷新max_sum的那一次才会把temp_start赋给真正的start。这避免了暂时看起来很有潜力、最终却没成为最优解的起点被输出。我强调一下这个细节因为很多版本的题解不展开讲这个面试里手写带下标的版本时容易写错。4.3 整数溢出与全负数数组边界实现Kadane算法时有一个坑很容易被忽略当数组是[-1, -2, -3, -4]这类全负数时正确答案是-1而不是0。如果你的max_sum初始化成0那最终就会错误地返回0。所以max_sum一定要初始化为float(-inf)或者在知道数组不为空的情况下初始化为nums[0]。另一个坑是整数溢出。考虑一个极端情况数组长度是10^5每个元素都是10^9那么整个数组的和是10^14量级超出了32位整数范围。如果你用的是C的int就会溢出。Leetcode的测试用例里没有设置这么极端的全正数大数组但在C实现中稳妥做法是把ans声明为long long或者直接使用INT_MIN但接受可能的溢出风险。我在面试中建议直接和面试官确认数值范围或者用long long一劳永逸。4.4 多语言实现对比除了Python我还整理了C和Java的常用实现面试时哪个顺手用哪个// C class Solution { public: int maxSubArray(vectorint nums) { int curSum 0; int maxSum INT_MIN; for (int x : nums) { curSum max(x, curSum x); maxSum max(maxSum, curSum); } return maxSum; } };// Java class Solution { public int maxSubArray(int[] nums) { int curSum 0; int maxSum Integer.MIN_VALUE; for (int x : nums) { curSum Math.max(x, curSum x); maxSum Math.max(maxSum, curSum); } return maxSum; } }// Go func maxSubArray(nums []int) int { curSum : 0 maxSum : nums[0] for _, x : range nums { if curSum 0 { curSum x } else { curSum x } if curSum maxSum { maxSum curSum } } return maxSum }可以说这四种语言的代码结构完全一致区别只在于语法细节。Kadane算法就是那种一旦你理解了在任何语言里都能五分钟写出来的算法。5. 从Kadane到进阶子数组问题还能怎么考5.1 分治解法线段树思想的雏形除了动态规划最大子数组和还有一个经典的O(nlogn)分治解法。思路是把数组分成左右两半最大子数组和可能完全在左半边、完全在右半边、或者跨越中点。前两种情况递归求解第三种情况从中间向两边扩展求出包含中间元素的最大和。这道题的分治解法的价值不在时间复杂度上——它比Kadane算法慢——而在于它包含了一个重要的思想合并区间时需要维护四个值——区间总和、区间最大前缀和、区间最大后缀和、区间最大子数组和。这四个值的合并方式正是线段树节点维护区间信息的标准套路。具体来说一个区间节点需要存储total整个区间的和leftMax区间内以左端点为起点的最大子数组和rightMax区间内以右端点为终点的最大子数组和maxSum区间内任意起终点的最大子数组和合并左区间L和右区间R时total L.total R.total leftMax max(L.leftMax, L.total R.leftMax) rightMax max(R.rightMax, R.total L.rightMax) maxSum max(L.maxSum, R.maxSum, L.rightMax R.leftMax)这个合并公式在LeetCode 53的分治版本里会出现在LeetCode 918环形数组里也会出现。如果你之后想攻克线段树问题先把这个合并逻辑吃透会非常有帮助。5.2 变体一环形数组的最大子数组和LeetCode 918题把nums变成了环形数组允许子数组跨越首尾相接。最直观的解法是转换思路环形数组的最大子数组和要么和普通数组一样出现在中间段要么跨越首尾。跨越首尾的情况可以转换为整个数组的和减去数组内部的最小子数组和。所以这道题可以在一次遍历中同时维护最大子数组和与最小子数组和最后比较两种情况的较大值def maxSubarraySumCircular(nums): total 0 max_sum cur_max float(-inf) min_sum cur_min float(inf) for x in nums: total x cur_max max(x, cur_max x) max_sum max(max_sum, cur_max) cur_min min(x, cur_min x) min_sum min(min_sum, cur_min) return max(max_sum, total - min_sum) if max_sum 0 else max_sum注意最后一行如果数组全是负数total - min_sum可能是0反而比正确答案大所以要判断max_sum 0。这个细节是环形数组版本最容易错的地方。5.3 变体二二维矩阵的最大子矩阵和把一维数组扩展到二维矩阵问题就变成了给定一个m×n矩阵找出和最大的子矩阵。基础解法是对矩阵的行做枚举固定上边界top和下边界bottom把这一块区域内每一列的数值累加成一维数组然后对一维数组跑Kadane算法。这样外层枚举top和bottom是O(m^2)内层Kadane是O(n)整体复杂度O(m^2·n)。对于100行左右的矩阵这个复杂度完全够用。这个思路是LeetCode 363题、以及最大子矩阵类面试题的标准解法而且也是一维Kadane最常见的扩展场景。5.4 变体三乘积最大子数组LeetCode 152题把加法换成乘法要求乘积最大的连续子数组。乍看之下和最大子数组和很像但有一个关键区别乘法里两个负数相乘会变成正数所以当前最小值也可能在下一步反转成最大值。因此我们需要同时维护以当前位置结尾的乘积最大值和最小值状态转移变为curMax max(x, preMax * x, preMin * x) curMin min(x, preMax * x, preMin * x)这里需要用到前一轮的preMax和preMin所以不能直接覆盖要先暂存。这个题目是最能体现动态规划状态设计需要结合运算性质的例子——加法不需要考虑符号反转乘法需要。6. 刷题与面试中的常见错误和高效路径6.1 最常见的四个错误我看了不少刷题群里的人提交的代码把高频错误总结成表格错误类型错误示例后果正确做法答案初始化为0maxSum 0全负数数组返回0而非最大负数初始化为float(-inf)或nums[0]未处理空数组直接访问nums[0]运行时异常判断空数组按需求返回0或抛出异常混淆curSum与maxSum最后返回curSum返回的是当前子数组和而非历史最大始终返回maxSum下标记录时忘记重置起点只用start不用tempStart输出错误子数组范围引入临时起点仅在刷新最大值时提交真正起点第四个错误在面试手写时暴露率极高。我曾经看到有候选人在白板上写一个记录起点终点的版本逻辑看起来通畅但实际跑用例[1,2,-5,3,4]输出的起点是0而不是3因为当curSum变小但没跌到负数时起点不应该变化而他简单地在每个元素处更新了起点。正确的是只有curSum 0重置时才可能更新临时起点。6.2 一道题串起整条知识脉络如果你想用一道题检验自己是否真的掌握了Kadane算法我建议你把这条链走一遍能快速写出O(n)的Kadane算法版本并解释状态定义。能写出记录起止下标的版本。能给出分治解法并说明合并时的四个值分别代表什么。能口述环形数组的转换思路并指出全负数时的边界。能在5分钟内把Kadane算法改写成乘积版本。这五步每一步都不长但它们覆盖了动态规划、分治、边界处理、变体迁移四个维度。能做到第五步的人对这道题的理解深度已经超过大部分刷题者了。6.3 刷题建议不要只追求ACLeetcode热题100的意义不在于让你把100道题的代码背下来而是每一道题都能延伸出一类问题的解法。最大子数组和就是一个典型的种子题目由它可以生长出环形数组、二维矩阵、乘积数组、树上最大路径和LeetCode 124等一串相关题目。124题虽然看起来是二叉树但核心思路还是一维Kadane的负数就丢弃思想的树形版本。我个人的刷题习惯是每AC一道题强制自己写一段这题和哪三道题有关联区别在哪里的笔记。这样刷题从我做过了变成我想通了长期积累下来面试时看到生题也能迅速定位到熟悉的思想框架。7. 从Kadane算法延伸出去的思维模型7.1 处理连续性问题时的通用思路最大子数组和这类问题有一个共同特征要求结果在一段连续的区间内。面对这种连续约束常见的动态规划状态定义就是以当前位置为结尾的某种最优值。这个定义几乎可以套用到所有连续子数组相关的问题上最长递增子序列可以不连续状态是以当前位置为结尾的最长递增子序列长度。最长连续递增序列必须连续状态同样是以当前位置为结尾的最长连续递增长度。最大子数组和状态是以当前位置为结尾的最大子数组和。区别只在于状态转移时前者需要向前遍历查找所有可能的衔接位置O(n^2)后者只需要看相邻位置O(n)。所以当你在面试中遇到连续子数组连续子串这类描述时优先考虑以i结尾的DP定义这是一个屡试不爽的突破口。7.2 为什么负数前缀果断丢弃是安全的Kadane算法的核心决策点就一个curSum变成负数后到底丢弃还是保留用数学语言说我们是在解一个最优化问题max_{0 i j n} sum(nums[i..j])这个问题的枚举空间是O(n^2)。DP优化的本质是sum(nums[i..j])可以分解为prefix[j] - prefix[i-1]其中prefix是前缀和数组。于是max_{0 i j n} (prefix[j] - prefix[i-1])固定j时要让这个值最大只需要让prefix[i-1]最小。也就是说在遍历j的过程中只要维护一个历史最小前缀和就能在O(1)时间内算出以j结尾的最大子数组和。这与Kadane算法是等价的def maxSubArray(nums): prefix_sum 0 min_prefix_sum 0 ans float(-inf) for x in nums: prefix_sum x ans max(ans, prefix_sum - min_prefix_sum) min_prefix_sum min(min_prefix_sum, prefix_sum) return ans这个视角的好处是当题目变成允许一次修改/删除某个元素或者子数组和不能超过某个阈值时前缀和加最小前缀的思路往往比直接的DP更容易扩展。我在面试中如果时间充裕会同时给出Kadane和前缀和两种解释面试官的反馈通常都很正面。7.3 前缀和与滑动窗口的边界有些读者可能会问最大子数组和能不能用滑动窗口我的回答是如果数组里存在负数滑动窗口就不能直接使用。滑动窗口适用场景是窗口内状态可以单调收缩的问题而负数会破坏这种单调性——你无法判断扩大窗口是让和变大了还是变小了。所以最大子数组和的问题正确出路是DP或前缀和滑动窗口留给无重复字符的最长子串和长度最小的子数组这类问题吧。在Leetcode的热题100里53题的另一层价值就是帮你建立什么情况下用滑动窗口什么情况下用DP的判断力。很多人在面试里只会背模板一碰到负数就翻车这恰恰说明基础逻辑没打通。8. 实战中的测试用例选择很多人在Leetcode上提交通过后就以为万事大吉但实际工程中往往没有那么多干净数据。我建议你至少用以下几组用例验证自己实现[1, 2, 3, 4]全是正数答案应该是总和10。[-1, -2, -3, -4]全是负数答案应该是-1。[5, -1, -2, 6]正负交替答案应该是8整个数组中间虽然有负数但没拖垮总体。[8, -10, 7, 1]前段有一个大的负数答案应该在最右侧的8而不是整体和6。[0, 0, -1]包含零答案应该0。这五组用例覆盖了正数、负数、零、正负混合四种情况能快速检验你的实现是否正确。一个值得注意的现象是很多人写出Kadane算法后想当然地认为遇到负数就应该重置但这在[5, -1, -2, 6]里是错的——整体和6比单独取6更大所以不能看到负数就断开而要看累积和是否仍然为正。Kadane算法用max(x, curSum x)这个式子精确地表达了这个判断而不是简单地遇到负数就重置。提示如果你在Leetcode上只想快速ACKadane算法四行代码就够了。但如果你把这道题当作面试题准备请务必理解状态转移方程的推导过程和边界细节。面试官考这道题的目的通常不是为了看你背没背过代码而是看你能不能把这个状态定义讲清楚。最后分享一个实用的刷题技巧每道题目AC后把官方题解里你没想到的解法也写一遍。53题我写了暴力、DP、Kadane、前缀和四个版本每写一遍理解就深一层。尤其是前缀和版本它让我后来做和可被K整除的子数组和为K的子数组数量这类题时几乎不需要重新思考直接迁移思路。这也是热题100的意义所在——每一道经典题都值得你多做几个版本而不是刷过就忘。