企业官网建设流程全解析

最大子数组和（也叫最大子段和）几乎是每个刷题人绕不开的第一道动态规划题。今天要拆解的这道题，编号是1749，全称是“任意子数组和的绝对值的最大值”。在很多动态规划入门题单里，它被排在最大子数组和之后，看起来只是加了一个“绝对值”，实际上一下把问题从单方向极值扩展成了双向极值。这篇就围绕它完整过一遍：从暴力想法出发，推导动态规划的状态设计，再介绍一种更简洁的前缀和极差解法，最后把调试时踩过的坑列清楚。不管你是刚接触DP的新手，还是刷题到一半想回头补基础的老手，这篇应该都能给你一些参考。

1. 为什么最大子数组和是入门DP的必修题

1.1 暴力解法的复杂度之痛

先回到最原始的问题：给定一个整数数组，求连续子数组的和的最大值。如果没学过DP，第一反应肯定是暴力枚举。枚举左端点 i，枚举右端点 j，再算区间和，三件事全干完是 O(n^3)；稍微优化一下，用前缀和把区间和的计算变成 O(1)，枚举复杂度降为 O(n^2)。看着还行，但一旦数组长度到 10^5 甚至 10^6，O(n^2) 直接爆炸。

我自己一开始也想过更“聪明”的滑动窗口，后来发现这题不能用滑动窗口。滑动窗口适合窗口有单调性质的问题，比如“和小于 K 的最长连续子数组”，因为右端点右移时，窗口内的收益可能单调变化。但最大子数组和没有这种单调性，加入一个负数可能让当前窗口直接失效，而窗口又不允许跳过负数重新开始，所以滑动窗口这条路走不通。

到这一步，几乎只能上动态规划。而动态规划的核心问题只有一个：怎么把“以任意区间为对象”的枚举，变成“以每个位置为锚点”的递推。

1.2 以“结尾位置”设计状态

经典的做法是把状态定义为：dp[i]表示以nums[i]结尾的子数组的最大和。

这个定义的好处是，它天然覆盖了所有子数组。任意一个子数组都有唯一的右端点，只要对每个右端点求出“以它为结尾的最大值”，再在所有右端点里取最大，答案就跑不掉。每个子数组要么选择延续dp[i-1]那段，要么从nums[i]重新开始，所以转移方程只有两条路：

dp[i] = max(dp[i-1] + nums[i], nums[i])

翻译成人话：到第 i 个位置时，要么把前面的最大连续段接上当前元素，要么前面的段整体不要了，自己单独作为新起点。

这个“延续还是重启”的决策，是理解这道题的关键。很多初学者会写错成dp[i] = max(dp[i-1], nums[i])，那就是掉进了“最长递增子序列”的思维定式。LIS 里可以跳过当前元素只取前面的结果，但连续子数组不行——dp[i]的定义强制包含nums[i]，所以第二项必须写成nums[i]，而不是保留前面的最优解。这正是“连续”和“非连续”在状态设计上的分水岭。

1.3 为什么入门DP总是拿它举例

因为它的状态转移只有一行，却包含了动态规划最基本的两个要素：最优子结构（局部最优递推出全局最优）和无后效性（dp[i]只依赖dp[i-1]，不关心更早的状态是怎么来的）。你不需要倒推数组，也不需要记忆化搜索，一维数组甚至两个变量就能解决。

但基础归基础，它引出的“在某类区间最值问题里，以端点作为状态锚点”的思路，可以平移到一大堆题上：最大子数组积、最长有效括号、打家劫舍……几乎都是同一套骨架。所以刷 DP 入门，先把这个模型刻在脑子里，后面遇到变体会省很多事。

2. 1749题的“绝对值”到底多在哪里

2.1 “绝对值”打破了单向极值

经典最大子数组和求的是和的最大值，隐含了一个假设：我们只关心正方向上的极端。但绝对值不一样，绝对值要求的是“离 0 最远”的子数组，可能是很大的正数，也可能是很小的负数。

举个最直接的例子：数组[-2, -1, -3]。最大子数组和是多少？答案是-1，也就是max(nums[i])。但这道题问的是绝对值最大，整个数组的和是-6，|-6| = 6，正确答案是 6。如果照着老思路算出最大子段和-1再取绝对值，得到 1，距离正确结果差了 6 倍。

这就是被“绝对值”三个字摆了一道的典型场景。它告诉我们：你不能只维护一个最大值方向，还必须同时维护最小值方向。最小子段和对应的子数组，取绝对值后很可能才是最终的赢家。

2.2 把问题拆成最大与最小两个方向

想清楚之后，题目就变成了两个经典子问题的组合：

• 先求所有子数组和中最大的那个，记作maxSub。
• 再求所有子数组和中最小的那个，记作minSub。
• 最终答案就是max(maxSub, -minSub)。

为什么这样就完备了？因为任意子数组的和无非三种情况：正数、负数、零。正数方向的最大值被maxSub抓住，负数方向绝对值最大的那个被minSub抓住后取负，而零不会比这两者更优。所以两个方向各自找到极值，整体答案就确定了。

这个“拆成两个方向”的思考方式，比一上来就纠结“怎么求绝对值的最大”要舒服得多。处理绝对值问题的时候，先把绝对值符号按定义拆开，绝大多数情况下都会变成两个更简单的问题。

2.3 数学化表述与严谨性验证

严谨一点，可以这样证明。

设任意子数组为S(l, r) = nums[l] + ... + nums[r]，它的右端点是 r。

如果S >= 0，那么它一定不超过以 r 结尾的最大子段和dpMax[r]，所以它也一定不超过所有dpMax的最大值，也就是maxSub。

如果S < 0，那么它一定不小于（也就是“大于等于”）以 r 结尾的最小子段和dpMin[r]，两边取负号，-S <= -dpMin[r]，也就是它的绝对值不超过-minSub。

所以任何子数组的绝对值都不超过max(maxSub, -minSub)。反过来，maxSub和-minSub本身都来源于某个具体的子数组，必然可达。上下界重合，答案就是max(maxSub, -minSub)。

这个证明同时解释了算法为什么正确，也解释了为什么不能用“最大子段和取绝对值”蒙混过关：因为最大子段和的方向只覆盖了正子数组，负方向的极端子数组它根本看不到。

3. 动态规划状态机：同时维护最大值和最小值

3.1 状态定义与转移方程

顺着上一节的结论，我们只需要把经典 Kadane 算法写两遍：

• maxEnding[i]：以nums[i]结尾的子数组的最大和。
• minEnding[i]：以nums[i]结尾的子数组的最小和。

转移方程对称地写：

maxEnding[i] = max(nums[i], maxEnding[i-1] + nums[i]) minEnding[i] = min(nums[i], minEnding[i-1] + nums[i])

minEnding的转移逻辑和maxEnding完全对称：当前位置要么单独成为一个最小段，要么把前面积累的最小段拼上当前元素。

很多代码里会把初值设成0，也就是maxEnding = 0, minEnding = 0，然后从第一个元素开始迭代。这样的效果等同于“空前缀的和为 0”，第一次迭代时max(x, 0 + x)和max(x, x)是等价的，所以不会出错。但要注意，这并不意味着可以返回空子数组，因为答案在迭代过程中只从具体元素对应的状态里取，不会专门取那个初始的 0。

3.2 空间优化与 Python 实现

dp数组在迭代中只用得到上一个位置的值，所以完全可以用两个滚动变量替代一整个数组。这也是入门 DP 里很常见的空间优化：先写出数组版本，再观察依赖关系，只保留需要的上一轮结果。

下面是完整的实现：

def maxAbsoluteSum(nums): ans = float('-inf') max_ending = 0 min_ending = 0 for x in nums: max_ending = max(x, max_ending + x) min_ending = min(x, min_ending + x) ans = max(ans, max_ending, -min_ending) return ans

时间复杂度 O(n)，空间复杂度 O(1)。从编码角度来说，这个解法几乎和经典最大子数组和一样短，只是多维护了一个min_ending，并在更新答案时多考虑了-min_ending。

3.3 边界条件与初值选择

边界问题是这类题最容易翻车的地方。先说ans的初值，如果设成 0，那么数组全为负数时会直接返回 0，而正确的答案是一个负数取绝对值后的正数。比如[-2, -1, -3]，全程最大子段和是 -1，最小子段和是 -6，正确答案 6，初始化为 0 的代码会错误地返回 0。所以ans必须设成一个足够小的值，比如float('-inf')或第一个元素的值。

再就是max_ending和min_ending的初值。用 0 初始化符合“空前缀不影响和”的习惯，而且因为转移方程里总是拿 0 加当前元素，结果不会偏离。如果更严谨一些，也可以先取nums[0]初始化两个变量，然后从第二个元素开始循环，效果一样。

另一个容易犯的错是把max_ending和min_ending混用。比如在更新min_ending时写成min(x, max_ending + x)，这会让“最小值”继承最大值方向的积累结果，状态完全错乱。你只需要记住：最大值和最小值一定要各走各的状态转移线，两条线互不干扰。

4. 另一种高维视角：前缀和与极差

4.1 子数组和与前缀和的等价关系

动态规划解法很常规，但 1749 题还有一个更优雅的做法，理解之后你对“子数组和”这个概念的认识会直接上一个台阶。

设前缀和数组pre，其中pre[0] = 0，pre[i]表示前 i 个元素的和。那么子数组nums[l..r]的和，就等于pre[r+1] - pre[l]。这是一个纯粹的差值关系。

所以“所有子数组和的绝对值的最大值”，等价于“前缀和数组中任意两个数的差值的绝对值的最大值”。而对一组数来说，任意两数的最大绝对值差值，就是这组数的最大值减最小值。注意这里的顺序问题：子数组要求r+1 >= l，但取绝对值后顺序无所谓，因为abs(a - b) == abs(b - a)。于是问题瞬间化简为：

答案 = max(pre) - min(pre)

这个视角不需要任何动态规划，只需要一遍扫描，维护当前前缀和、当前前缀和最大值、当前前缀和最小值。

4.2 极差法的实现

def maxAbsoluteSum(nums): max_pre = 0 min_pre = 0 cur = 0 for x in nums: cur += x max_pre = max(max_pre, cur) min_pre = min(min_pre, cur) return max_pre - min_pre

为什么max_pre和min_pre要从 0 开始？因为pre[0] = 0，空前缀也必须参与比较。如果漏掉 0，遇到全正数组[1, 2, 3]，前缀和是1, 3, 6，最大 6、最小 1，极差 5，可是正确结果显然是整个数组和 6。补上 0 之后，极差变成 6，答案才对。

4.3 两种解法的对比

DP 解法的思路更“正统”，状态转移直接对应决策过程，适合作为入门训练。前缀和极差解法更巧妙，推导路径短，代码也短，但前提是你对前缀和的工具足够敏感。两者的复杂度都是 O(n) 时间、O(1) 空间，实际提交性能几乎没有差别。

我个人的看法：考试或者面试时能写出 DP 解法就已经合格，前缀和极差法属于加分项，能体现对问题本质的理解。平时练习建议两种都写一遍，尤其是极差法，它能帮你把“子数组和 = 前缀和之差”这个等价关系刻进脑子里，后面很多子数组问题都用得上。

5. 常见错误与调试实录

5.1 最容易踩的三个坑

第一个坑是答案初始化为 0。用[-2, -1, -3]一测就现原形，正确输出是 6，初始化成 0 的代码输出 0。这个坑的本质是混淆了“允许空子数组”和“不允许空子数组”。题目要求连续非空子数组，答案不能凭空取 0。

第二个坑是只维护最大值方向，最后直接返回abs(maxEnding)。[-2, -1, -3]里maxEnding最终是 -1，取绝对值是 1，而正确答案是 6。你损失的恰恰是“负得最深”的那段，也就是和最小的子数组。

第三个坑出现在前缀和极差法里，漏掉了空前缀 0。前面已经说过，全正数组会因此少算。这类错误在样例不是极端型时很容易漏过去，所以测试用例一定要覆盖全正、全负、全零、正负交替四类。

5.2 一套可复用的测试用例

下面这几个用例建议刷题时直接拿来当验证集，尤其是第一和第二个，基本覆盖了这道题所有容易出错的边界。

如果用任意一种实现跑完这组用例没出错，这道题的边界基本就稳了。

5.3 调试思路

调试这类 DP 题，最有效的办法不是盯着代码干瞪眼，而是把中间量打出来。尤其是max_ending和min_ending这两个变量，打印出来之后，你能直观看到每个位置的两个候选值是怎么演化的。如果发现min_ending在某一步突然跳成了一个很大的正数，那基本可以断定状态转移写串了，比如不小心用了max_ending去更新它。

另外，如果测试用例很多但总是差一两个数，可以写一个 O(n^2) 的暴力版本做对拍。暴力枚举所有子数组直接算绝对值，数据量几百的时候毫无压力。对拍是排查隐蔽边界问题的通用手段，比凭空猜要快得多。

6. 从这道题看“正负双轨”DP套路

6.1 最大和最小同时维护的适用场景

1749 题的价值不只是让你多会一道题，而是引出了一个高频套路：当序列问题同时受正负两个方向影响时，状态往往要同时维护最大值和最小值。

最典型的例子是求乘积最大子数组。因为两个负数相乘会变成正数，最小的乘积乘上一个负数后可能反超最大值。所以那道题不仅要维护max_prod，还必须维护min_prod，转移时三者一起取最大最小。“正负双轨”这个思路，本质上和这道题维护最大最小子段和是同一个道理。

另一个相关场景是环形数组的最大子数组和。常规解法的思路是：要么最大值不出现在跨越边界的地方，直接用普通 Kadane；要么最大值跨越了边界，那等价于整个数组和减去一个最小子段和。你看，这里也需要求最小子段和。所以说这道入门题不是孤立的点，它其实是后面一堆题目共同的地基。

6.2 遇到“最大最小+子数组”时怎么下手

以后再碰到类似描述，先不要急着套模板。第一步，把问题用最朴素的枚举语言写出来：所有子数组，什么属性要最大或最小。第二步，判断这个属性能不能通过“以右端点结尾”这个锚点做递推。第三步，如果涉及正负混合，问自己一个问题：是不是要同时维护两个方向？

这道题从“最大子段和”到“绝对值的最大子段和”，只加了一个绝对值，解法就从单变量变成了双变量。很多看似复杂的问题，其实都是在基础模型上叠加一个新约束，然后把新约束翻译成对状态数量的要求。翻译过来的结论往往很朴素：一个方向不够，那就维护两个方向；两个方向也不够，那就上矩阵、上树形结构。动态规划的入门阶段，能把“方向不够就加状态”这个感觉找对，比背一堆模板有用得多。

这套思路多跑几道题之后，再回头看 1749 就会觉得很自然：最大值和最小值同时维护本来就是解决绝对值问题的通用姿势。以后刷到任何“绝对值最大”“乘积最大”“环形最大”这类字眼，第一反应都不会再是套公式，而是想清楚到底有几个方向在互相竞争。