最近在刷前些年算法竞赛的历届试题碰到一道叫“最大子阵”的C题卡了我一阵子。表面上看就是给一个矩阵求元素和最大的子矩阵但真动手写起来才发现里面的门道不少怎么从一维的最大子段和推广到二维、怎么压复杂度、全负数矩阵怎么处理、要不要输出具体坐标每个点都能引申出一堆细节。这篇就把我的完整思路、代码和踩过的坑都复盘一遍适合正在准备算法类比赛、想把二维动态规划练扎实的同学。1. 从一维到二维最大子阵的破题关键1.1 先搞定一维的最大子段和最大子阵的问题本质上是“最大子段和”的二维版本。一维版本大家应该不陌生给定一个整数数组 a[0..m-1]求一个连续的子数组使它的和最大。比如[-2, 1, -3, 4, -1, 2, 1, -5, 4]最大子段是[4, -1, 2, 1]和为 6。一维的经典动态规划做法非常简洁。记dp[j]表示“以 a[j] 结尾的最大子段和”转移方程是dp[j] max(a[j], dp[j-1] a[j])写成滚动变量就是这样long long cur 0, best LLONG_MIN; for (int j 0; j m; j) { cur max(a[j], cur a[j]); best max(best, cur); }这里的cur其实只有两种选择要么从 a[j] 重新开始要么接上前面的段。如果前面的段已经变成负数那还不如从当前位置重新开始。这个思想是整个最大子阵算法的地基后面所有二维操作都要用到它。1.2 二维矩阵的压缩思路二维矩阵里一个子阵由四条边界决定上边界 top、下边界 bottom、左边界 left、右边界 right。我们的目标是让这个矩形内部的元素和最大。最直觉的做法当然是枚举四条边界四层循环加上求和复杂度轻松爆炸。但仔细观察能发现一个关键转化如果固定了上边界 top 和下边界 bottom那么每一列的所有元素就可以“压扁”成一个数——把从 top 到 bottom 这一列的元素累加起来。这样一来矩阵就从二维退化成了一个一维数组接下来只需要在这个数组上求最大子段和。举个例子假设有这样的 3 行 3 列矩阵1 -2 3 -4 5 -6 7 -8 9如果取 top 0, bottom 2那么三列分别累加得到col[0] 1 - 4 7 4col[1] -2 5 - 8 -5col[2] 3 - 6 9 6。此时一维数组是[4, -5, 6]最大子段和是max(6, 4-565)也就是 6。这对应原矩阵里只取第三列那一竖条和确实最大看起来没问题。这里的精髓就是二维子矩阵的和等于行压缩后一维数组的连续子段和。行压缩把每一列从 top 到 bottom 的所有元素合并成单个值子段选择对应原矩阵的左边界和右边界。这一层关系想通了整个题就只剩下枚举上下边界的事情。2. 算法复杂度的三种姿势直觉、暴力、优化2.1 四层循环的暴力代价最容易想到的暴力做法是枚举左上角和右下角for (int top...) for (int left...) for (int bottom...) for (int right...)然后计算四个角围起来的矩形和。如果再用一个循环累加那就是五层循环复杂度 O(n² × m² × 平均矩形面积)几十个数据点就能让程序跑到天荒地老。就算用前缀和把矩形求和优化成 O(1)四层循环本身的枚举量仍然是 O(n² × m²)。当 n、m 都是 500 时循环次数超过 625 亿完全不可接受。2.2 行压缩后的三层循环模型采用“固定上下边界 列压缩”的方案后枚举结构变成了这样枚举上边界 top从 0 到 n-1。枚举下边界 bottom从 top 到 n-1。在每一轮 bottom 递增时把当前行累加进 col 数组。对 col 数组做一次一维最大子段和更新全局答案。第一层枚举 top 共 n 次第二层 bottom 平均约 n/2 次第三层一维 DP 需要 O(m)。所以总复杂度是 O(n² × m)。如果 n 和 m 差不多大这就是 O(n³) 级别500 的规模下大约一亿多次运算用 C 跑完全没问题。这个方案还有个小优化习惯在最内层的 one-dimensional DP 之前col 数组的更新也要 O(m)这同样被包含在 O(n² × m) 里。但注意 col 的更新和 DP 都是顺序扫描常数很小实际运行速度是令人满意的。2.3 n 与 m 悬殊时的转置优化如果矩阵是“瘦高型”或者“扁宽型”比如 n1000、m50那么直接按上面的写法复杂度是 1000² × 50 5000 万还好。但反过来 n50、m1000 时50² × 1000 250 万差别巨大。所以一个很实用的技巧是如果 n m就把矩阵转置让枚举上下边界的那一维尽可能短。转置之后原来行数较多的矩阵变成行数较少的矩阵算法会快很多。不过要注意如果需要输出具体的子阵坐标转置会导致坐标互换输出前得再换回来。如果只求最大和转置没有任何副作用放心用。为了直观对比我把三种方案列在下表里方案枚举结构时间复杂度可接受规模约四层循环 实时求和上下左右全枚举O(n²m²)n,m ≤ 30四层循环 二维前缀和上下左右全枚举O(n²m²)n,m ≤ 50行压缩 一维 DP只枚举上下边界O(n²m)n,m ≤ 500再大也有优化余地行压缩方案的“压缩”动作非常优雅它把“选左右边界”这个二维问题交给了一维最大子段和去处理省掉了左、右两层循环。3. C可运行代码与逐段注释3.1 完整实现下面这段代码是最基础的版本只求最大子阵和不输出坐标。我加了注释方便直接对照思路看。#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorll a(n, vectorll(m)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } ll ans LLONG_MIN; for (int top 0; top n; top) { vectorll col(m, 0); for (int bottom top; bottom n; bottom) { // 将第 bottom 行累加到 col 上col[j] 表示第 j 列从 top 到 bottom 的和 for (int j 0; j m; j) { col[j] a[bottom][j]; } // 对 col 数组求最大子段和 ll best LLONG_MIN; ll cur 0; for (int j 0; j m; j) { cur max(col[j], cur col[j]); best max(best, cur); } ans max(ans, best); } } cout ans \n; return 0; }核心逻辑就两个循环嵌套。外层 top 每换一次col 清零一次内层 bottom 从 top 往下走每多走一行就把新遇到的矩阵行加进 col。这样保证枚举到任意一对(top, bottom)时col 数组都精确表示“这些行叠加后的一维投影”。3.2 为什么用 long long 而不是 int我在很多地方见过有人用 int 做这道题结果跑大数据时莫名其妙 WA。原因很朴素矩阵元素可能是正数也可能是负数极端情况下成千上万个绝对值很大的数累加int 很容易溢出。比如 nm500每个元素是 10 万最大子阵和可能到几百亿远超 32 位 int 的范围。所以定义矩阵、col、cur、best、ans 时我全部用long long。在竞赛环境里long long的运算速度比 int 略慢但这个差距完全可以忽略而它换来的安全性却非常值得。记住一个原则涉及连续求和的题目不确定范围时优先 long long。另外LLONG_MIN是climits里的最小值常量用bits/stdc.h会自动引入。如果你不想用这个头文件也可以自己写const ll INF -(1LL 60);。这里用LLONG_MIN会遇到一个问题如果LLONG_MIN加上一个负数会溢出。但我的代码里cur max(col[j], cur col[j])在第一次运算时cur是 0 而不是LLONG_MIN所以不会出现负数加LLONG_MIN的情况。best只是被赋值为LLONG_MIN然后被cur覆盖也不会参与加减运算安全。3.3 输出最大和的验证用例我随便构造一个矩阵来跑一下3 3 1 -2 3 -4 5 -6 7 -8 9按平常感觉能取的最大子阵是第三列整体[3, -6, 9]和为 6。运行上面的程序输出就是 6。再测一个全是负数的矩阵2 2 -1 -2 -3 -4最大子阵就是最不亏的那个负数-1程序输出 -1。这说明初始化成LLONG_MIN的做法在全负数场景下也能正确工作。4. 边界条件与我实际踩过的坑4.1 全负数矩阵的初始化陷阱我第一次写这个题时用了一维最大子段和最常见的写法“如果 cur 小于 0 就重置为 0”。代码如下ll cur 0, best 0; for (int j 0; j m; j) { cur col[j]; if (cur 0) cur 0; best max(best, cur); }这个版本在数组存在正数时没问题但如果整个矩阵全是负的best会一直停留在 0而正确答案应该是最大的那个负数。解决方式有两种一是把best初始化为LLONG_MIN并且在累加前先判断“单独取 col[j] 是否比接上前面的段更好”也就是写成cur max(col[j], cur col[j])二是保持原来的写法但每次更新后把col[j]也纳入比较例如best max(best, cur)不够还要best max(best, col[j])。第一种写法更干净推荐直接用。4.2 一行或一列矩阵的退化情况如果题目给的是 1×m 的矩阵那这个问题的二维性质就消失了。我们的算法依然能跑top 只会取 0bottom 也只取 0col 数组就是第一行本身一维 DP 求出的就是最大子段和完全正确。如果给的是 n×1 的矩阵也就是一列数情况类似。top 和 bottom 的枚举相当于在一列里选连续的一段col 数组只有一个元素一维 DP 退化为“选单个元素或这一列的总和”的比较。由于只有一列最大子阵其实就是这一列中的最大连续段也就是一维最大子段和也能正确输出。这个退化特性说明算法有很好的通用性不用担心特判。4.3 枚举顺序导致的重复计算问题行压缩的代码里col 数组是在 bottom 循环里“一次次累加”的。很多人第一次写会下意识地在 bottom 循环内把 col 重新用三层循环清零再计算比如写成for (int top 0; top n; top) { for (int bottom top; bottom n; bottom) { vectorll col(m, 0); for (int r top; r bottom; r) { for (int j 0; j m; j) col[j] a[r][j]; } // 一维 DP ... } }这样虽然也能算对但多了一层 r 循环复杂度变成 O(n³ × m)比预期多了 n 倍。正确的做法是让 col 数组随着 bottom 递增滚动累加bottom 从 top 开始每增加 1只需要把新进入范围的那一行加进去之前的结果全都保留着。这也是前缀和思想在行方向上的应用。5. 进阶需求把最大子阵的坐标也输出5.1 记录上下边界的时机很多竞赛题的升级版本会要求“输出最大子阵的左上角和右下角坐标”。这时候不能只维护一个 ans 值还得在每次更新 ans 时记录当时的 top、bottom、left、right。上下边界容易记录当一维 DP 得到的best大于当前ans时说明以当前 top 和 bottom 为上下界的压缩数组中找到了一个更大的子段。这时直接更新ans_top top; ans_bottom bottom;即可。5.2 一维DP中记录左右边界左右边界的记录稍微麻烦一点需要在一维 DP 里同时维护“当前段起点”。核心逻辑是从 j 开始一个新的段时记录l j当cur col[j]比col[j]更大时继续沿用之前的 l当cur更新为col[j]时说明旧段断掉l 更新为 j当best被更新时把left l; right j;。一个比较稳妥的实现是ll best LLONG_MIN; ll cur 0, segL 0; int tmpLeft 0, left 0, right 0; for (int j 0; j m; j) { if (cur col[j] col[j]) { cur cur col[j]; } else { cur col[j]; tmpLeft j; } if (cur best) { best cur; left tmpLeft; right j; } }这里tmpLeft表示当前以 j 结尾的这段的起点候选值。当cur决定从col[j]重新开始时起点就变为 j当cur继续接前面的段时起点保持之前的tmpLeft。只有当cur超过当前best时才把最终坐标固定下来。如果题目只要求输出任意一个最优解那相等时不必更新坐标如果要求最靠左上角的解则在cur best的条件改为cur best并且同时比较 top、bottom 大小细节不少需要按题目要求调整。5.3 坐标回溯的注意事项输出坐标时最容易被忽略的是“bottom 的更新时机”。因为 col 数组是滚动累加的当你在某个 bottom 下更新了 ans 和坐标后面 bottom 继续增大时 col 已经变了但 ans 和坐标已经保存下来不会受影响。真正容易出错的是top 外层循环每换一次col 必须清零同时tmpLeft、left、right这些临时变量最好重新初始化。另外如果使用了“转置优化”那么记录的 top 和 left 之间的关系会发生互换。假设原来的行数大于列数我们转置后枚举的是原矩阵的列记录下来的 top/bottom 其实是原矩阵的列区间left/right 才是原矩阵的行区间。输出时要把坐标调换回去不然就 WA。6. 竞赛变形题的应对思路6.1 最大绝对值子阵有的题目不要求“和最大”而是要求“和的绝对值最大”。这个问题比普通最大子阵多了一层思考绝对值最大的子阵要么是正数最大的子阵要么是负数最小的子阵。负数最小的子阵其实就是把所有元素取反之后的最大子阵但要注意它对应的是原矩阵中的最小子阵和绝对值后可能最大。实现方式也很直接在行压缩数组 col 上分别求出最大子段和和最小子段和。最大子段和用原来的curMax max(col[j], curMax col[j])最小子段和用curMin min(col[j], curMin col[j])。最后取max(abs(maxBest), abs(minBest))作为答案。这个思路相当于把一维的做法在二维上跑两遍代码量增加不多但能应对更多变种。6.2 子阵元素个数受限或恰好K个的扩展如果题目追加“子阵必须包含至少 K 个元素”或者要求所有子阵中元素个数不超过某个限制情况就复杂了。一维部分可以用长度受限的最大子段和比如滑动窗口配合前缀和在 O(m) 内求“长度不超过 L 的最大子段和”二维部分再套用行压缩枚举。这类扩展题往往不能直接搬模板但对最大子阵的压缩思想熟悉之后至少能快速定位“瓶颈在哪个维度”再针对性地优化。6.3 个人经验总结刷了这道题之后我最大的体会是二维问题不要急着写四层循环先想想能不能压缩成一维。最大子阵就是典型的“枚举一个维度、在另一个维度上跑一维算法”的模型。代码本身很短但每一步都有值得琢磨的细节初始化、滚动累加、边界场景、坐标记录任何一个环节出了问题都可能让人调试很久。如果非要再给一条建议那就是把测试数据准备充分。全正数、全负数、单行、单列、随机混合数据都跑一遍再交到评测系统里比一次一次盲试要高效得多。算法竞赛比的不仅是思路更是把这些细节打磨到条件反射的程度。
最近在刷前些年算法竞赛的历届试题碰到一道叫“最大子阵”的C题卡了我一阵子。表面上看就是给一个矩阵求元素和最大的子矩阵但真动手写起来才发现里面的门道不少怎么从一维的最大子段和推广到二维、怎么压复杂度、全负数矩阵怎么处理、要不要输出具体坐标每个点都能引申出一堆细节。这篇就把我的完整思路、代码和踩过的坑都复盘一遍适合正在准备算法类比赛、想把二维动态规划练扎实的同学。1. 从一维到二维最大子阵的破题关键1.1 先搞定一维的最大子段和最大子阵的问题本质上是“最大子段和”的二维版本。一维版本大家应该不陌生给定一个整数数组 a[0..m-1]求一个连续的子数组使它的和最大。比如[-2, 1, -3, 4, -1, 2, 1, -5, 4]最大子段是[4, -1, 2, 1]和为 6。一维的经典动态规划做法非常简洁。记dp[j]表示“以 a[j] 结尾的最大子段和”转移方程是dp[j] max(a[j], dp[j-1] a[j])写成滚动变量就是这样long long cur 0, best LLONG_MIN; for (int j 0; j m; j) { cur max(a[j], cur a[j]); best max(best, cur); }这里的cur其实只有两种选择要么从 a[j] 重新开始要么接上前面的段。如果前面的段已经变成负数那还不如从当前位置重新开始。这个思想是整个最大子阵算法的地基后面所有二维操作都要用到它。1.2 二维矩阵的压缩思路二维矩阵里一个子阵由四条边界决定上边界 top、下边界 bottom、左边界 left、右边界 right。我们的目标是让这个矩形内部的元素和最大。最直觉的做法当然是枚举四条边界四层循环加上求和复杂度轻松爆炸。但仔细观察能发现一个关键转化如果固定了上边界 top 和下边界 bottom那么每一列的所有元素就可以“压扁”成一个数——把从 top 到 bottom 这一列的元素累加起来。这样一来矩阵就从二维退化成了一个一维数组接下来只需要在这个数组上求最大子段和。举个例子假设有这样的 3 行 3 列矩阵1 -2 3 -4 5 -6 7 -8 9如果取 top 0, bottom 2那么三列分别累加得到col[0] 1 - 4 7 4col[1] -2 5 - 8 -5col[2] 3 - 6 9 6。此时一维数组是[4, -5, 6]最大子段和是max(6, 4-565)也就是 6。这对应原矩阵里只取第三列那一竖条和确实最大看起来没问题。这里的精髓就是二维子矩阵的和等于行压缩后一维数组的连续子段和。行压缩把每一列从 top 到 bottom 的所有元素合并成单个值子段选择对应原矩阵的左边界和右边界。这一层关系想通了整个题就只剩下枚举上下边界的事情。2. 算法复杂度的三种姿势直觉、暴力、优化2.1 四层循环的暴力代价最容易想到的暴力做法是枚举左上角和右下角for (int top...) for (int left...) for (int bottom...) for (int right...)然后计算四个角围起来的矩形和。如果再用一个循环累加那就是五层循环复杂度 O(n² × m² × 平均矩形面积)几十个数据点就能让程序跑到天荒地老。就算用前缀和把矩形求和优化成 O(1)四层循环本身的枚举量仍然是 O(n² × m²)。当 n、m 都是 500 时循环次数超过 625 亿完全不可接受。2.2 行压缩后的三层循环模型采用“固定上下边界 列压缩”的方案后枚举结构变成了这样枚举上边界 top从 0 到 n-1。枚举下边界 bottom从 top 到 n-1。在每一轮 bottom 递增时把当前行累加进 col 数组。对 col 数组做一次一维最大子段和更新全局答案。第一层枚举 top 共 n 次第二层 bottom 平均约 n/2 次第三层一维 DP 需要 O(m)。所以总复杂度是 O(n² × m)。如果 n 和 m 差不多大这就是 O(n³) 级别500 的规模下大约一亿多次运算用 C 跑完全没问题。这个方案还有个小优化习惯在最内层的 one-dimensional DP 之前col 数组的更新也要 O(m)这同样被包含在 O(n² × m) 里。但注意 col 的更新和 DP 都是顺序扫描常数很小实际运行速度是令人满意的。2.3 n 与 m 悬殊时的转置优化如果矩阵是“瘦高型”或者“扁宽型”比如 n1000、m50那么直接按上面的写法复杂度是 1000² × 50 5000 万还好。但反过来 n50、m1000 时50² × 1000 250 万差别巨大。所以一个很实用的技巧是如果 n m就把矩阵转置让枚举上下边界的那一维尽可能短。转置之后原来行数较多的矩阵变成行数较少的矩阵算法会快很多。不过要注意如果需要输出具体的子阵坐标转置会导致坐标互换输出前得再换回来。如果只求最大和转置没有任何副作用放心用。为了直观对比我把三种方案列在下表里方案枚举结构时间复杂度可接受规模约四层循环 实时求和上下左右全枚举O(n²m²)n,m ≤ 30四层循环 二维前缀和上下左右全枚举O(n²m²)n,m ≤ 50行压缩 一维 DP只枚举上下边界O(n²m)n,m ≤ 500再大也有优化余地行压缩方案的“压缩”动作非常优雅它把“选左右边界”这个二维问题交给了一维最大子段和去处理省掉了左、右两层循环。3. C可运行代码与逐段注释3.1 完整实现下面这段代码是最基础的版本只求最大子阵和不输出坐标。我加了注释方便直接对照思路看。#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorll a(n, vectorll(m)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } ll ans LLONG_MIN; for (int top 0; top n; top) { vectorll col(m, 0); for (int bottom top; bottom n; bottom) { // 将第 bottom 行累加到 col 上col[j] 表示第 j 列从 top 到 bottom 的和 for (int j 0; j m; j) { col[j] a[bottom][j]; } // 对 col 数组求最大子段和 ll best LLONG_MIN; ll cur 0; for (int j 0; j m; j) { cur max(col[j], cur col[j]); best max(best, cur); } ans max(ans, best); } } cout ans \n; return 0; }核心逻辑就两个循环嵌套。外层 top 每换一次col 清零一次内层 bottom 从 top 往下走每多走一行就把新遇到的矩阵行加进 col。这样保证枚举到任意一对(top, bottom)时col 数组都精确表示“这些行叠加后的一维投影”。3.2 为什么用 long long 而不是 int我在很多地方见过有人用 int 做这道题结果跑大数据时莫名其妙 WA。原因很朴素矩阵元素可能是正数也可能是负数极端情况下成千上万个绝对值很大的数累加int 很容易溢出。比如 nm500每个元素是 10 万最大子阵和可能到几百亿远超 32 位 int 的范围。所以定义矩阵、col、cur、best、ans 时我全部用long long。在竞赛环境里long long的运算速度比 int 略慢但这个差距完全可以忽略而它换来的安全性却非常值得。记住一个原则涉及连续求和的题目不确定范围时优先 long long。另外LLONG_MIN是climits里的最小值常量用bits/stdc.h会自动引入。如果你不想用这个头文件也可以自己写const ll INF -(1LL 60);。这里用LLONG_MIN会遇到一个问题如果LLONG_MIN加上一个负数会溢出。但我的代码里cur max(col[j], cur col[j])在第一次运算时cur是 0 而不是LLONG_MIN所以不会出现负数加LLONG_MIN的情况。best只是被赋值为LLONG_MIN然后被cur覆盖也不会参与加减运算安全。3.3 输出最大和的验证用例我随便构造一个矩阵来跑一下3 3 1 -2 3 -4 5 -6 7 -8 9按平常感觉能取的最大子阵是第三列整体[3, -6, 9]和为 6。运行上面的程序输出就是 6。再测一个全是负数的矩阵2 2 -1 -2 -3 -4最大子阵就是最不亏的那个负数-1程序输出 -1。这说明初始化成LLONG_MIN的做法在全负数场景下也能正确工作。4. 边界条件与我实际踩过的坑4.1 全负数矩阵的初始化陷阱我第一次写这个题时用了一维最大子段和最常见的写法“如果 cur 小于 0 就重置为 0”。代码如下ll cur 0, best 0; for (int j 0; j m; j) { cur col[j]; if (cur 0) cur 0; best max(best, cur); }这个版本在数组存在正数时没问题但如果整个矩阵全是负的best会一直停留在 0而正确答案应该是最大的那个负数。解决方式有两种一是把best初始化为LLONG_MIN并且在累加前先判断“单独取 col[j] 是否比接上前面的段更好”也就是写成cur max(col[j], cur col[j])二是保持原来的写法但每次更新后把col[j]也纳入比较例如best max(best, cur)不够还要best max(best, col[j])。第一种写法更干净推荐直接用。4.2 一行或一列矩阵的退化情况如果题目给的是 1×m 的矩阵那这个问题的二维性质就消失了。我们的算法依然能跑top 只会取 0bottom 也只取 0col 数组就是第一行本身一维 DP 求出的就是最大子段和完全正确。如果给的是 n×1 的矩阵也就是一列数情况类似。top 和 bottom 的枚举相当于在一列里选连续的一段col 数组只有一个元素一维 DP 退化为“选单个元素或这一列的总和”的比较。由于只有一列最大子阵其实就是这一列中的最大连续段也就是一维最大子段和也能正确输出。这个退化特性说明算法有很好的通用性不用担心特判。4.3 枚举顺序导致的重复计算问题行压缩的代码里col 数组是在 bottom 循环里“一次次累加”的。很多人第一次写会下意识地在 bottom 循环内把 col 重新用三层循环清零再计算比如写成for (int top 0; top n; top) { for (int bottom top; bottom n; bottom) { vectorll col(m, 0); for (int r top; r bottom; r) { for (int j 0; j m; j) col[j] a[r][j]; } // 一维 DP ... } }这样虽然也能算对但多了一层 r 循环复杂度变成 O(n³ × m)比预期多了 n 倍。正确的做法是让 col 数组随着 bottom 递增滚动累加bottom 从 top 开始每增加 1只需要把新进入范围的那一行加进去之前的结果全都保留着。这也是前缀和思想在行方向上的应用。5. 进阶需求把最大子阵的坐标也输出5.1 记录上下边界的时机很多竞赛题的升级版本会要求“输出最大子阵的左上角和右下角坐标”。这时候不能只维护一个 ans 值还得在每次更新 ans 时记录当时的 top、bottom、left、right。上下边界容易记录当一维 DP 得到的best大于当前ans时说明以当前 top 和 bottom 为上下界的压缩数组中找到了一个更大的子段。这时直接更新ans_top top; ans_bottom bottom;即可。5.2 一维DP中记录左右边界左右边界的记录稍微麻烦一点需要在一维 DP 里同时维护“当前段起点”。核心逻辑是从 j 开始一个新的段时记录l j当cur col[j]比col[j]更大时继续沿用之前的 l当cur更新为col[j]时说明旧段断掉l 更新为 j当best被更新时把left l; right j;。一个比较稳妥的实现是ll best LLONG_MIN; ll cur 0, segL 0; int tmpLeft 0, left 0, right 0; for (int j 0; j m; j) { if (cur col[j] col[j]) { cur cur col[j]; } else { cur col[j]; tmpLeft j; } if (cur best) { best cur; left tmpLeft; right j; } }这里tmpLeft表示当前以 j 结尾的这段的起点候选值。当cur决定从col[j]重新开始时起点就变为 j当cur继续接前面的段时起点保持之前的tmpLeft。只有当cur超过当前best时才把最终坐标固定下来。如果题目只要求输出任意一个最优解那相等时不必更新坐标如果要求最靠左上角的解则在cur best的条件改为cur best并且同时比较 top、bottom 大小细节不少需要按题目要求调整。5.3 坐标回溯的注意事项输出坐标时最容易被忽略的是“bottom 的更新时机”。因为 col 数组是滚动累加的当你在某个 bottom 下更新了 ans 和坐标后面 bottom 继续增大时 col 已经变了但 ans 和坐标已经保存下来不会受影响。真正容易出错的是top 外层循环每换一次col 必须清零同时tmpLeft、left、right这些临时变量最好重新初始化。另外如果使用了“转置优化”那么记录的 top 和 left 之间的关系会发生互换。假设原来的行数大于列数我们转置后枚举的是原矩阵的列记录下来的 top/bottom 其实是原矩阵的列区间left/right 才是原矩阵的行区间。输出时要把坐标调换回去不然就 WA。6. 竞赛变形题的应对思路6.1 最大绝对值子阵有的题目不要求“和最大”而是要求“和的绝对值最大”。这个问题比普通最大子阵多了一层思考绝对值最大的子阵要么是正数最大的子阵要么是负数最小的子阵。负数最小的子阵其实就是把所有元素取反之后的最大子阵但要注意它对应的是原矩阵中的最小子阵和绝对值后可能最大。实现方式也很直接在行压缩数组 col 上分别求出最大子段和和最小子段和。最大子段和用原来的curMax max(col[j], curMax col[j])最小子段和用curMin min(col[j], curMin col[j])。最后取max(abs(maxBest), abs(minBest))作为答案。这个思路相当于把一维的做法在二维上跑两遍代码量增加不多但能应对更多变种。6.2 子阵元素个数受限或恰好K个的扩展如果题目追加“子阵必须包含至少 K 个元素”或者要求所有子阵中元素个数不超过某个限制情况就复杂了。一维部分可以用长度受限的最大子段和比如滑动窗口配合前缀和在 O(m) 内求“长度不超过 L 的最大子段和”二维部分再套用行压缩枚举。这类扩展题往往不能直接搬模板但对最大子阵的压缩思想熟悉之后至少能快速定位“瓶颈在哪个维度”再针对性地优化。6.3 个人经验总结刷了这道题之后我最大的体会是二维问题不要急着写四层循环先想想能不能压缩成一维。最大子阵就是典型的“枚举一个维度、在另一个维度上跑一维算法”的模型。代码本身很短但每一步都有值得琢磨的细节初始化、滚动累加、边界场景、坐标记录任何一个环节出了问题都可能让人调试很久。如果非要再给一条建议那就是把测试数据准备充分。全正数、全负数、单行、单列、随机混合数据都跑一遍再交到评测系统里比一次一次盲试要高效得多。算法竞赛比的不仅是思路更是把这些细节打磨到条件反射的程度。
