在某个动态规划入门刷题清单里最大子数组和几乎是每个新手都要过的一关。说实话我第一次看到“任意子数组和的绝对值的最大值”这个题目时心里想的是这跟最大子段和有什么区别结果一写就发现如果只套经典的 Kadane 算法拿到的可能是错答案。这一题的关键在于“绝对值”三个字它逼着你从正负两个方向同时思考问题。这篇我会把这道题拆开讲清楚状态为什么那样定义、转移方程怎么来的然后给出三种能 AC 的写法最后分享一些我实际调试时踩过的坑。1. 先看清题目在问什么不只是最大子数组和1.1 一句话翻译题目题目给一个整数数组要求任意连续非空子数组的和的绝对值的最大值。注意两个限定词连续子数组必须是原数组中连续的一段不能跳着取。非空至少要包含一个元素空数组的和是 0不在考虑范围内。例如[-1, 2, -3, 3]最大子数组和是 2也就是单独取[2]。但题目问的是绝对值的最大值单独取[-3]的和是 -3绝对值是 3所以答案应该是 3 而不是 2。如果只背过经典最大子段和的模板上来直接跑一遍 Kadane就会在这里翻车。这个例子说明绝对值把负方向的“最小子段和”也带进了竞争范围。最大子段和只追正数方向的最大值而这个题要同时追正的最大和负的最小。1.2 暴力枚举为什么必死新手最容易想到的办法是枚举所有子数组对每个子数组求和再取绝对值最大。两层循环枚举左右端点已经 O(n^2)如果每次再累加一遍就是 O(n^3)。即使先用前缀和把区间和优化成 O(1)整体仍是 O(n^2)。当 n 到 10^5 时O(n^2) 是 10^10 量级跑完基本要等到天荒地老。所以这里必须找 O(n) 或者 O(n log n) 的做法。动态规划的思路恰好能做到 O(n)这也正是这个题被放进“入门 DP”章节的原因。1.3 绝对值带来的对称性启发绝对值函数有个很朴素的分段性质|S| S 当 S 0 |S| -S 当 S 0也就是说一个子数组和的绝对值特别大只有两种可能它本身就是很大的正数或者它本身就是很小的负数。那我们是不是可以分别求出两类东西所有子数组和中最大的正数是多少所有子数组和中最小的负数是多少然后把这两个值都算出来比较谁的绝对值更大。这个想法就是正解的雏形。经典的 Kadane 算法能解决第一个问题那么把 max 换成 min就能解决第二个问题。题目要求绝对值最大值答案就是max(最大子段和, -最小子段和)。2. 核心原理为什么答案藏在最大子段和与最小子段和里2.1 从经典 Kadane 状态说起最大子段和经典状态定义是这样的设f[i]表示以第 i 个元素结尾的所有子数组中和最大的那个值。注意“以 i 结尾”这个约束它保证了状态之间的递推关系是连续的。转移方程f[i] max(f[i-1] nums[i], nums[i])为什么只有两个选择因为以 i 结尾的子数组要么把 nums[i] 接到以 i-1 结尾的最优子数组后面要么自己单独成为一个子数组从 i 重新开始。这件事没法绕过也不可能从更早的位置“飞过来”因为子数组必须连续。举个例子nums [3, -1, 2]f[0] 3f[1] max(3 (-1), -1) 2对应[3, -1]f[2] max(2 2, 2) 4对应[3, -1, 2]最终答案是所有 f 里的最大值 4。这个状态定义很关键它把“任意子数组”这个无限集合压缩成了“以每个位置结尾的一类子数组”然后用转移方程递推。理解了这个后面所有扩展都围绕它展开。2.2 把最小子段和也当成一等公民对称地设g[i]表示以 i 结尾的所有子数组中和最小的那个值。转移方程g[i] min(g[i-1] nums[i], nums[i])逻辑和最大版本完全镜像要么接着前面最差的子数组继续累加要么从当前位置重新开始。唯一区别只是把max换成min。沿用刚才的例子g[0] 3g[1] min(3 - 1, -1) -1g[2] min(-1 2, 2) 1这里的最小值是 -1。于是一个比较自然的做法是遍历每个位置记录abs(f[i])和abs(g[i])的最大值作为全局答案。可能会有读者疑惑f[i]不一定单调g[i]也不一定单调那在某个位置取到的绝对值最大为什么能代表全局因为任何一个子数组必然有一个确定的右端点 i它一定被包含在“以 i 结尾”的候选集合里。所以我们只需要对每个 i 检查一次就能覆盖所有子数组。2.3 一个不等式搞定证明用数学语言把上一节的直觉写严瑾一些。记maxSub是所有子数组和的最大值minSub是所有子数组和的最小值对于任意一个子数组它的和 S 满足minSub S maxSub于是max(|S|) max( maxSub, -minSub )为什么因为绝对值函数在正区间单调递增在负区间单调递减。S 的绝对值要最大只可能发生在 S 取到最大正值或最小负值的两个端点。这就是这题最优解的全部原理。而maxSub和minSub恰好分别由刚才的f和g两个 DP 链给出。所以最终答案就是answer max(max(f[i]), -min(g[i]))等价地遍历时直接维护ans max(ans, abs(f[i]), abs(g[i]))也可以两个写法结果相同。2.4 非空子数组约束不能丢有些经典题解会把 Kadane 转移写成f[i] max(0, f[i-1] nums[i])这种写法求的是“允许空子数组”的最大子段和或者说它把最终结果当作maxSub来用但遇到全负数数组时会返回 0。新鲜刷题的人看到全负数用例挂掉往往不知道问题出在哪。本题要求非空子数组所以转移必须写成f[i] max(f[i-1] nums[i], nums[i])nums[i]这个选项保证了从当前元素重新开始不会因为前面是负的就把当前元素也丢掉。同理g[i]也要写成min(g[i-1] nums[i], nums[i])而不是min(0, g[i-1] nums[i])。这一点看起来小却是这道题和很多变种题的真正分水岭。3. 三种实现从最直白到最简洁3.1 双 DP 数组版状态一目了然最直接的方式是开两个数组分别存f和g跑完再取答案。def max_abs_sum(nums): n len(nums) dp_max [0] * n dp_min [0] * n dp_max[0] nums[0] dp_min[0] nums[0] ans abs(nums[0]) for i in range(1, n): dp_max[i] max(dp_max[i - 1] nums[i], nums[i]) dp_min[i] min(dp_min[i - 1] nums[i], nums[i]) ans max(ans, abs(dp_max[i]), abs(dp_min[i])) return ans这个版本的空间是 O(n)。好处是每个位置的状态都能看到打印出来可以很直白地观察递推过程适合第一次接触这道题的人理解。坏处是数组长度大时没必要多花这 O(n) 内存因为转移只依赖前一个位置的值。3.2 滚动变量版Kadane 的常数空间形态因为f[i]只依赖f[i-1]g[i]i只依赖g[i-1]所以用两个变量滚动更新就够了。def max_abs_sum(nums): cur_max nums[0] cur_min nums[0] ans abs(nums[0]) for x in nums[1:]: cur_max max(cur_max x, x) cur_min min(cur_min x, x) ans max(ans, abs(cur_max), abs(cur_min)) return ans每次循环里cur_max表示以当前元素结尾的最大子段和cur_min表示以当前元素结尾的最小子段和。两者互不干扰可以同时更新。这个写法时间复杂度 O(n)空间复杂度 O(1)是面试时最推荐给面试官看的版本。理由很简单它把状态压缩到了理论下界同时代码依然短小清晰。注意变量更新顺序没有讲究因为cur_max和cur_min计算都不需要对方的新值。3.3 前缀和最大跨度版另一种世界观除了动态规划这题还有一个非常漂亮的 O(n) 解法前缀和。设prefix[i]表示前 i 个元素的和其中prefix[0] 0。那么子数组[l, r)的和就是prefix[r] - prefix[l]题目要求这个差的绝对值的最大值。换句话说是在前缀和数组里找一对下标使两个前缀和相差最大取绝对值。那答案自然就是max(prefix) - min(prefix)代码可以写成def max_abs_sum(nums): prefix 0 mn 0 mx 0 for x in nums: prefix x mn min(mn, prefix) mx max(mx, prefix) return mx - mn这里mn初始化为 0mx也初始化为 0代表空前缀。这个细节很重要当数组全为正数时最小值出现在空前缀 0 处最大值在末尾mx - mn就等于总和当数组全为负数时最大值出现在空前缀 0 处最小值在末尾mx - mn就等于负总和的绝对值正确。为什么max(prefix) - min(prefix)一定对应一个合法子数组假设最大前缀出现在下标 i最小前缀出现在下标 j。如果i j那么子数组[j, i)的和就是prefix[i] - prefix[j]正好等于跨度。如果i j那么子数组[i, j)的和是prefix[j] - prefix[i]这个值是负数绝对值也等于跨度。所以在绝对值意义下两个端点谁先谁后并无影响要么正着取要么反着取都能找到一个非空连续区间达到这个差值。我第一次看到这个写法时觉得很惊艳它绕开了“以 i 结尾”的状态思维直接从区间和的差结构出发。但它的缺点是需要额外理解前缀和数组的语义对新手不如滚动变量版直观。3.4 三种解法对比方法时间复杂度空间复杂度适合场景双 DP 数组O(n)O(n)教学演示、打印状态调试滚动变量O(n)O(1)面试手写、日常刷题前缀和跨度O(n)O(1)追求代码极简、理解区间和本质实际做题选哪种都行。我个人建议第一次做用双 DP 数组理解原理理解透之后再默写滚动变量版前缀和版本作为额外收获知道存在即可。4. 边界条件与踩坑实录4.1 初始化 0 陷阱全负数输入直接翻车这是最典型的坑。如果初始化写成cur_max 0 cur_min 0然后从第一个元素开始循环那么当输入全为负数时比如[-5, -2, -3]第一轮cur_max max(0 - 5, -5) -5但如果你错误地写成max(0, cur_max x)之类就会变成 0即使cur_max max(cur_max x, x)初始化 0 也会导致cur_max首轮变成max(-5, -5) -5好像问题不大但关键在ans初始值如果是 0全负数数组就会一直保留ans 0最终输出 0而正确答案是 5。所以初始化要么cur_max cur_min ans nums[0]从第二个元素开始循环要么循环内对所有位置判断。我见过太多人在全负数用例上卡住一查全是初始值问题。4.2 溢出问题int 不够用怎么办C 或 Java 环境下如果数组长度和数值范围较大前缀和或者子段和可能超过 32 位整型范围。比如元素个数 10^5每个元素绝对值 10^9那么累加和可能是 10^14 量级int 直接溢出。稳妥做法是用long long或long来存储long long curMax nums[0]; long long curMin nums[0]; long long ans llabs(nums[0]);注意绝对值函数用llabs不是abs否则可能截断几何意义上的正确结果。Python 没有这个烦恼因为整数无限大但理解这个点能帮助你用其他语言时少踩坑。4.3 一个隐藏条件子数组是否允许为空刷题时先看题目描述确认子数组是否可以为空。这题明确是连续非空子数组所以转移方程中必须保留nums[i]这个“单独成段”的选项。如果把max(0, ...)版本抄过来在混合正负数的数组上运气好也能过但全负数数组一定会错。所以做题前先跟面试官或题目确认约束再做对应取舍。这本身也是考察点。4.4 对拍测试法我怎么确认代码是对的刷题时我习惯写一个暴力解法当基准随机生成小数组做对拍。暴力解法直接枚举所有子区间用前缀和求区间和取绝对值最大def brute(nums): n len(nums) prefix [0] for x in nums: prefix.append(prefix[-1] x) ans 0 for i in range(n): for j in range(i 1, n 1): ans max(ans, abs(prefix[j] - prefix[i])) return ans然后随机生成长度不超过 8、取值在[-10, 10]的数组把三种解法和暴力的输出逐一比对。只要跑几百组随机数据全对边界情况再手动补上全正、全负、零交替几组代码就可以放心提交。我在实际做题时发现这种对拍法比单纯看题解快得多它能逼着你把每一步的真实行为暴露在数据面前。5. 从这题辐射开最大子段和家族与通用套路5.1 变种题对照表掌握这道题之后最大的收获是**“维护两个方向的极值”**这个套路。它不只在绝对值问题里有效在更大一类题目里都通用。变种问题核心关键思路经典最大子数组和求最大非空子段和单个 Kadane 链环形最大子数组和子数组可以跨越首尾答案等于 max(普通最大子段和, 总和 - 最小子段和)乘积最大子数组子数组乘积最大同时维护最大乘积和最小乘积因为负数相乘会反转大小任意子数组和的绝对值的最大值本题绝对值最大同时维护最大子段和与最小子段和二维矩阵最大子矩阵和矩阵中最大子矩阵和枚举行范围压缩成一维后跑 Kadane你会发现min版本的状态不是多余的镜像而是解决环形、乘积、绝对值等一系列问题的核心工具。5.2 二维扩展枚举行压成一维再 Kadane举个例子二维矩阵求最大子矩阵和。思路是把“矩阵”转化成“一维数组”枚举矩阵的起始行和结束行然后逐列累加得到一个长度为列数的临时数组在这个临时数组上跑 Kadane。这里的临时数组某个位置的值是“从起始行到结束行这一段在该列上的高度总和”。因为子矩阵在原矩阵中必须是连续行、连续列逐列累加正好保住了这种连续性。如果在二维版本里再要求绝对值的最大值你只需要在压缩后的临时数组上同时跑 max 和 min 两条链。所以这道 1749 题的思路可以直接平移到更高维度。5.3 面试答题与代码风格建议面试手写这道题时我建议按这个顺序讲先跟面试官确认子数组是否非空简述暴力 O(n^2) 为什么不行定义f[i]和g[i]两个状态解释转移方程口头说明最终答案是max(maxSub, -minSub)上滚动变量版代码最后提一句可以用前缀和max - min再优化成更短的实现。这种表达方式既展示了 DP 的状态设计能力又展现了复杂度的敏感度印象分会好很多。代码风格上变量名不要用x1、x2建议用curMax、curMin一看就知道含义。边界初始化写在开头注释里比如“子数组非空所以从 nums[0] 开始”既提醒自己也方便面试官理解。最后再分享一个小习惯这道题的三个解法我都建议手推一遍例子尤其是全负数[-3, -1, -2]和正负交替[1, -2, 3, -4]。手动推一遍之后你对“为什么必须维护 min 这条链”会有肌肉记忆下次遇到乘积最大子数组或者环形数组就不会只是背模板而是真的知道状态为什么这样设计。