优化)
最大子矩阵这道题，四个字看着简单，实际上考场上不知道卡了多少人。我第一次认真啃它，是在准备某高校复试机试的时候，题目描述就一句话：给定一个 n 阶整数矩阵，每个格子里都是整数，求一个元素和最大的子矩阵，输出这个最大值。暴力能过吗？n 只有 100 的时候，你枚举左上角和右下角，组合数就是 10^4 量级，每个再算一次区域内求和，整体往 10^8 以上走，运气好能卡过去，n 一旦到 200 或者要求输出具体坐标，基本就悬了。这道题真正的考点不是“你能不能算出来”，而是“你能不能把复杂度压到 O(n^3)”。它背后的核心，就是经典的一维最大子数组问题的二维推广。这篇文章适合正在准备复试机试、或者刷题想彻底弄懂来龙去脉的读者，我会把从暴力到前缀和再到降维打击的完整路线拆开讲，顺便把考场上的那些坑一次性说清楚。
1. 先看清题目在问什么
1.1 题意拆解：为什么不能直接套二维 DP
先明确题目语义。给定一个 n×n 的矩阵，每个格子可能是正数、负数或零，要求选出一个由连续行和连续列组成的矩形区域，让区域内所有数字之和最大，输出这个最大值。这里的“连续”很关键，子矩阵不能拆成多个不相邻的块，也不能旋转变形，就是规规矩矩一个矩形。
很多人第一反应是“这不就是一维最大子段和的二维版吗，直接定义 dp[i][j] 表示以 (i,j) 为右下角的最大子矩阵和”。这个方向想了一半，但直接定义状态会出问题：一维最大子段和里，dp[i] 能清晰表达“以 i 结尾的连续段”；可是二维里，同一个右下角坐标对应了无数种可能的矩形高度和宽度，左上角到底在哪里，右下角自己的状态根本说不清。换句话说，子矩阵需要在行方向和列方向同时连续，两个方向叠加之后，一维那个“以 x 结尾”的状态不够用了。所以不能照搬一维的状态转移，必须换一种组织方式。
还有一个容易忽略的细节：题目问的是“最大和”，不要求输出子矩阵本身时，问题会简单一些；但如果像某些真题那样，要求在最大和的同时输出左上角和右下角坐标，实现时就得多记录几个变量。建议从准备阶段就把坐标输出版一起练了，考场上万一遇到，不会慌了手脚。
1.2 从暴力到优化：复杂度到底卡在哪
最直白的暴力做法是四层循环枚举左上角坐标 (x1, y1) 和右下角坐标 (x2, y2)，再用两层循环把矩形里的所有元素加起来求区域和。枚举左上角是 O(n^2) 种可能，右下角也是 O(n^2) 种，求和又是 O(n^2)，整体就是 O(n^6)。n=10 的时候大概 10^6 次运算，没问题；n=50 的时候到了 1.56×10^10 这个量级，开始吃力；n=100 的时候直接破 10^12，任何机试环境都不可能等它跑完。
第一个常规优化是二维前缀和。预处理出 prefix[i][j] 表示从 (1,1) 到 (i,j) 这个矩形区域的元素总和，之后任意子矩阵的和都可以用容斥原理 O(1) 算出来，整体复杂度降到 O(n^4)。n=100 时大约 10^8 次操作，部分机试环境卡着时限勉强能过。但很多题目会把 n 放到 300 甚至 500，O(n^4) 依然扛不住。
这就是为什么这道题的标准解法定在 O(n^3)。思路核心是：行方向用枚举覆盖所有可能，列方向用一维最大子数组算法一次搞定。行枚举是 O(n^2)，列方向处理是 O(n)，合起来 O(n^3)，n=500 时大约 1.25×10^8 次运算，这才是复试机试要的复杂度水平。
2. 核心思路：把二维压成一维
2.1 一维最大子数组：Kadane 算法的直觉
在讲二维之前，先把一维的最大子数组和问题彻底搞透。给定一个数组 a，找出一段连续元素，使它们的和最大。经典解法是 Kadane 算法，也是动态规划的一种简单形式。
核心维护两个量：cur 表示“以当前位置结尾的连续段的最大和”，best 表示“全局最大和”。从头到尾遍历一遍，每个位置更新一次：
cur = max(a[i], cur + a[i]); best = max(best, cur);这条转移式的意思是，站在一个新的元素面前，你只有两个选择：要么从当前元素重新开始一个新的连续段，要么把这个元素接到前面已经形成的连续段后面。cur 如果已经累加成负数，说明前面那段不值得继续持有，果断从当前元素重新开始；如果 cur 还是正的，再接下去继续积累大概率更优。
这里有一个经常被误解的点：为什么数组里全是负数时，这个算法仍然正确？因为当 cur + a[i] 小于 a[i] 时，转移式会自动选择 a[i] 单独成段。遍历完后，best 自然就是数组中最大的那个负数，而不会是 0。这正好符合“子数组不能为空”的题目语义。
我在给同学讲的时候喜欢用一个持仓类比：想象你在做连续日期的股票交易，每天可以决定是否继续持有前一天的仓位，或者清仓从今天重新开始。cur 就是当前连续持仓的累计盈亏，一旦账面变亏，就果断换仓；best 则是你曾经达到过的最高累计盈利。这个类比能帮你牢牢记住转移式的含义，也方便迁移到二维场景。
2.2 固定上下边界后，问题自动降维
二维到一维的桥梁，是“列压缩”这个操作。想象一个子矩阵由第 top 行到第 bottom 行之间的连续若干行构成，把这些行同一列的数字全部相加，会得到一个新的数组 tmp，其中 tmp[col] 表示第 col 列在这个行区间内的元素和。
那么关键结论来了：对于固定的 top 和 bottom，原矩阵中所有“行范围恰好是 top 到 bottom”的子矩阵的最大和，等于一维数组 tmp 的最大连续子段和。为什么？因为行方向已经被你框死了，剩下的只是“在这个列压缩后的数组里，选一段连续列区间作为子矩阵的左右边界”，这完完全全就是一维 Kadane 解决的问题。
整个过程可以这样组织：外层枚举上边界 top，内层枚举下边界 bottom，每次从 top 到 bottom 累加出 tmp，然后对 tmp 跑一次 Kadane，更新全局答案。枚举上下边界的组合数是 O(n^2)，每对上下界跑一次 O(n) 的 Kadane，总复杂度 O(n^3)。这个复杂度里，n^2 是逃不掉的，因为我们必须覆盖所有可能的行区间；但列区间不用再枚举了，因为一维算法自己就能找出最优的连续段。
有人可能会问，假如最优子矩阵的行范围很小，比如只有一行，这个枚举会漏掉吗？不会。top 等于 bottom 的情况本来就包含在双循环里，此时 tmp 就是那一行本身，Kadane 求出的就是这一行内部的最大连续段。单行、单列、全矩阵，所有情况都被覆盖到了。
2.3 列前缀和：让压缩这一步更快
实现“列压缩”时，有两种主流做法，区别只在计算 tmp 的方式。
做法一：固定 top 之后，随着 bottom 往下扩展，用一个临时数组持续累加当前行。这样当枚举到某对 (top, bottom) 时，tmp 已经自然表示 top 到 bottom 的列压缩结果，不需要额外的求和时间。
做法二：预处理列方向的前缀和。设 colPrefix[i][k] 表示第 k 列从第 1 行到第 i 行的元素总和，那么第 k 列在 top 到 bottom 行之间的和，就是 colPrefix[bottom][k] - colPrefix[top - 1][k]，可以 O(1) 得到 tmp 的每个位置。
两种做法的整体复杂度都是 O(n^3)，区别在于常数和代码风格。做法一更省内存、写法更直接；做法二在需要反复查询不同行区间同一列的累加值时更通用，也更容易扩展到多组询问的场景。对复试机试来说，我更推荐做法一，理由在后面代码部分会说明。
复杂度上再抠一点：外层枚举 top 有 n 种，内层枚举 bottom 平均 n/2 种，每对上下界里又有 n 个列的累加和 n 次 Kadane 操作，总计算量大约是 n^3 / 2 的量级，实际跑起来非常快。这也是为什么 n 到 500 时它依然能在一秒多内稳定通过。
3. 完整实现与关键细节
3.1 考场推荐写法：固定上边界加动态累加
直接给出我最推荐在考场上写的版本：固定 top，动态累加 tmp，调用一维 Kadane。完整代码如下：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll NEG_INF = -(1LL << 60); ll maxSubArray(ll arr[], int len) { if (len <= 0) return 0; ll cur = arr[0]; ll best = arr[0]; for (int i = 1; i < len; i++) { cur = max(arr[i], cur + arr[i]); best = max(best, cur); } return best; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<vector<ll>> a(n, vector<ll>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } ll ans = NEG_INF; for (int top = 0; top < n; top++) { vector<ll> tmp(n, 0); for (int bottom = top; bottom < n; bottom++) { // 把 bottom 这一行累加进 tmp for (int col = 0; col < n; col++) { tmp[col] += a[bottom][col]; } // tmp 代表 top~bottom 这组行区间的列压缩结果 ans = max(ans, maxSubArray(tmp.data(), n)); } } cout << ans << '\n'; return 0; }这段代码的逻辑链非常清晰：top 固定后，每次 bottom 往下走一行，就把新的一行加进 tmp，因此进入 maxSubArray 时，tmp 恰好等于从 top 到 bottom 的列压缩数组。跑完 Kadane 后更新 ans。整个过程不需要额外维护前缀和数组，也不容易出现下标偏移问题。
这里要特别注意 maxSubArray 内部的处理。cur 初始化成 arr[0]，best 也初始化成 arr[0]，转移式用的是 cur = max(arr[i], cur + arr[i])，这不是随手写的，是为了处理“所有元素都是负数”的情况。如果你把 cur 初始化成 0，转移式写成 cur = max(0, cur + arr[i])，矩阵全负时答案会错误地输出 0，题目往往不会给你这种仁慈。
3.2 另一种实现：列前缀和版本
如果你希望更通用、或者想练习前缀和思想，可以写成列前缀和版本：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll NEG_INF = -(1LL << 60); ll maxSubArray(ll arr[], int len) { if (len <= 0) return 0; ll cur = arr[0]; ll best = arr[0]; for (int i = 1; i < len; i++) { cur = max(arr[i], cur + arr[i]); best = max(best, cur); } return best; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<vector<ll>> a(n + 1, vector<ll>(n + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; } } vector<vector<ll>> colPrefix(n + 1, vector<ll>(n + 1, 0)); // colPrefix[i][j] 表示第 j 列前 i 行的和 for (int j = 1; j <= n; j++) { for (int i = 1; i <= n; i++) { colPrefix[i][j] = colPrefix[i - 1][j] + a[i][j]; } } ll ans = NEG_INF; vector<ll> tmp(n + 1, 0); for (int top = 1; top <= n; top++) { for (int bottom = top; bottom <= n; bottom++) { for (int col = 1; col <= n; col++) { tmp[col] = colPrefix[bottom][col] - colPrefix[top - 1][col]; } // tmp[1..n] 是有效数据，传入 tmp + 1 让函数从 tmp[1] 开始读 ans = max(ans, maxSubArray(tmp.data() + 1, n)); } } cout << ans << '\n'; return 0; }两个版本复杂度完全相同，做题时必须选一个自己最不会写错的。我个人推荐动态累加版，原因很简单：列前缀和版本需要额外处理 1 下标偏移，调用 maxSubArray 时得小心翼翼地传 tmp.data() + 1，一旦写错就是数组越界或者少算一列，调试起来很折腾。动态累加版的下标天然从 0 开始，和常见写法一致，出错概率更低。
但前缀和版的思想值得掌握，因为当你遇到“给定一个矩阵，有多组询问，每次问某个行区间内的最大子矩阵”这类变体时，前缀和是绕不开的基础设施。
3.3 全负矩阵与空子矩阵的语义
我记得有一次模拟赛，样例里专门给了个全负矩阵，好多同学都输出 0，然后被扣分。原因就是上面说的：Kadane 中“允许空区间”和“不允许空区间”的处理方式完全不同。
语义如果允许取空子矩阵，那么空的子矩阵和为 0，全负矩阵时正确答案确实是 0。做法是把 cur 初始化为 0，转移式写成 cur = max(0, cur + arr[i])。语义如果不允许取空矩阵，也就是子矩阵至少要包含一个格子，那么全负矩阵时正确答案是最大的那个负数。做法是 cur 和 best 都从 arr[0] 开始。
复试机试的“最大子矩阵”题，几乎都是后一种语义，因为题目要的是“选一个子矩阵”，空矩阵在几何上不构成一个矩形。做题前先看题目描述里有没有“非空”两个字，或者直接看样例数据，全负样例输出若是负数，那么必然是“非空”语义。
我的判断方法是：只要题目没明确说“可以选空子矩阵”，一律按非空处理，答案初始化为一个足够小的负数，而不是 0。这能避免大多数初始化导致的全负矩阵翻车。
4. 高频踩坑点与排查技巧
4.1 初始化错了，全负矩阵直接翻车
初始化是这道题最容易错的地方。具体来说有两个位置：
第一，全局答案 ans 初始化。如果写成 ll ans = 0，在矩阵全负时，任何子矩阵的和都不可能大于 0，但 ans 的初始值 0 会一直保留到最后，导致输出 0。正确做法是初始化为一个非常小的数，比如 -(1LL << 60) 或者 LLONG_MIN。
第二，Kadane 函数内部的 cur 和 best 初始化。如果写成 cur = 0，转移式写成 cur = max(0, cur + arr[i])，本质上是在允许“空子段”，和题意冲突。正确做法是从 arr[0] 开始，转移式保持 cur = max(arr[i], cur + arr[i])。
这两个位置有一个写错，全负矩阵的样例就会挂掉。而很多题目的样例数据偏偏就喜欢放一组全负，用来卡只会背模板的人。
4.2 单行、单列、n=1 的边界自测
边界条件这块，我建议在本地对拍时专门准备三个用例：
n=1 时，矩阵只有一个数字。如果这个数字是 -5，正确答案应该是 -5 而不是 0。Kadane 函数接收长度为 1 的数组时，for 循环一次都不执行，best 直接等于 arr[0]，所以逻辑正确。但要注意 maxSubArray 函数里对 len 的检查，如果 len 是 0 会有问题，但正常输入下不会出现 len=0。
单行矩阵，比如 1×5。枚举 top 和 bottom 时只能都是 0 那一行，tmp 就是这一行本身，Kadane 直接求这一行的最大连续段。单列矩阵同理，枚举完所有 top/bottom 后，tmp 长度为 1，每次 Kadane 返回的就是那一列在行区间内的和，本质上是在所有行区间里找最大连续行段，等价于把列方向转置后的一维问题。
很多同学在本地测试时只跑正常随机矩阵，忽略这些退化输入，结果上了考场遇到单行单列直接卡住。我的习惯是写完第一版，先手动输入 n=1、单行、单列这三个用例，确认输出符合预期，再开始随机对拍。
4.3 输入输出相关的小坑
先说输入。部分机试环境里，矩阵的每行末尾可能有空格，用 cin 读取完全不受影响。但如果你习惯用 scanf，注意和 ios::sync_with_stdio(false) 混用会导致读取异常，二选一就行。
再说多组数据。有的题目会在输入描述里写“输入可能包含多组测试数据，以 EOF 结束”，这种就必须写成 while (cin >> n) 的循环结构，每组数据独立计算并输出一行结果。只看一组的话，样例能过，但提交后只能通过部分测试点。
输出方面，要求输出最大值后换行，这个别漏。如果还用 printf 和 cout 混着输出，也可能出现缓冲区排序问题，尽量统一。
4.4 用随机对拍验证正确性
准备阶段最有效的验证手段是“对拍”。思路很简单：写两个程序，一个是暴力但绝对正确的版本，一个是你优化的 O(n^3) 版本，再用随机数据生成器批量喂给两个程序，比较输出是否一致。
暴力版可以不用 O(n^6)，用二维前缀和优化到 O(n^4) 即可，实现起来也快。随机数据生成器让 n 取 1 到 8，元素取 -10 到 10 的小范围，这样可以保证穷举时不会错过边角情况。
一个简单的数据生成器代码：
#include <bits/stdc++.h> using namespace std; int main() { srand(time(0)); int n = rand() % 8 + 1; cout << n << '\n'; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << rand() % 21 - 10 << ' '; } cout << '\n'; } return 0; }然后用 shell 循环跑对拍：
for i in $(seq 1 500); do ./gen > data.in ./brute < data.in > b.out ./fast < data.in > f.out diff b.out f.out || break done如果 500 组随机数据全部一致，代码基本可以放心。如果中途 diff 出差异，就用那一组数据反复调试，往往能很快定位到是初始化问题还是边界问题。对拍不是浪费时间，它能一次性把你自己没意识到的逻辑漏洞暴露出来。
4.5 别忘了 best 是实时更新的
我在批改练习代码时，见过有人把 Kadane 写成先算完整个 cur 序列，最后再取 max。这样也能得到正确答案，但容易漏掉一个关键点：best 必须在每个位置都更新，而不是只在循环结束后更新。原因是 cur 可能在中途达到一个很高的值，后面被连续负数拖累变低，如果只在最后取 cur 的最大值，就会丢掉中间那个最高峰。Kadane 的“全局最优”本质上是“所有局部最优的最大值”，每一步都要记录。
5. 同源变体与后续扩展
5.1 输出子矩阵坐标的进阶版
有些复试机试不止要求输出最大和，还要求输出对应的左上角和右下角坐标。这时候需要在 Kadane 里额外记录区间端点。实现思路是：在 cur 被重置为 arr[i] 时，把当前区间左右端点都设为 i；在 cur 累加 arr[i] 时，把右端点更新为 i；当 best 被更新时，同步记录此时的区间左右端点。
二维场景下，还要在更新全局 ans 时，记录当前的 top 和 bottom，以及 Kadane 返回的最优区间左右端点。最后输出时，左上角是 (top, left)，右下角是 (bottom, right)。注意如果代码统一使用 0 下标，而题目要求 1 下标，输出时全部加 1。这个“输出坐标加 1”的细节，每年都有人挂在上面。
如果题目还要求“多个答案输出任意一个”或者“输出字典序最小”，那就需要再额外增加比较逻辑，但核心框架不变。建议把记录坐标写成一个独立函数，避免在主函数里堆太多全局变量。
5.2 最大全 1 子矩阵：直方图方案
这是“最大子矩阵”最常见的变体：矩阵里只有 0 和 1，求一个全 1 子矩阵的最大面积。注意这里不能用前面直接求元素和的办法，因为全 1 矩阵的面积不是“和”的最大化，而是矩形宽乘高的最大化，和元素总和是两回事。
标准做法是逐行处理。维护一个数组 height[j]，表示从当前行往上数，第 j 列连续 1 的个数。遇到 a[i][j] 是 1，height[j] 加 1；遇到 0，height[j] 清零。然后对于每一行，把 height 数组当作一个直方图，用单调栈求“直方图最大矩形面积”。逐行做，总复杂度 O(n^2)。
单调栈的核心是：每个柱子 i，向左找到第一个高度小于 height[i] 的位置，向右找到第一个高度小于 height[i] 的位置，这两个位置之间的宽度乘以 height[i] 就是以该柱子高度为高的最大矩形面积。逐列处理，取最大。这个变体在复试机试里出现的频率很高，建议单独把“最大矩形面积”这道题练熟。
5.3 最大正方形：另一条 DP 路线
如果题目规定了子矩阵必须是正方形，就不能再用枚举上下边界加 Kadane 的思路了，而是有更简单的 DP。定义 dp[i][j] 表示以 (i,j) 为右下角的最大全 1 正方形边长。状态转移为：
if (a[i][j] == 1) { dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1; } else { dp[i][j] = 0; }为什么是取三个方向的最小值？因为一个以 (i,j) 为右下角的正方形，要同时保证左边、上边和左上角三个方向都至少存在对应边长的全 1 正方形，三者全部满足，才能扩展出更大的正方形。取最小值就是在找“短板”。这个题目路线和最大子矩阵和完全不同，做题时注意区分。
5.4 其他值得留意的扩展
“最大子矩阵”这个母题还有很多变体，比如把矩阵复制一份拼接成环形，求环上的最大子矩阵和；比如给矩阵每个格子加权，求带权最大子矩阵；比如给定 m 次询问，每次问某个行区间内的最大子矩阵。这些扩展大多是在基础 O(n^3) 框架上加一层数据结构优化，复试一般不会考到那么深，但如果你能把基础版本的原理彻底吃透，遇到这些变体时至少能看出“它是在考什么”。
我个人带练复试备考时有一个体会：这道题之所以高频出现，不是因为它算法有多难，而是因为它是“一维算法向二维迁移”的经典范本。你一旦想明白“固定上下边界之后，剩下的就是一维 Kadane”，整道题就从玄学变成了套路。先别急着背代码，拿一张纸画一个 3×3 的小矩阵，手动枚举两组上下边界，把每一列的数字加起来，自己感受一下“列压缩”到底在做什么。这个动作做完，后面所有相关变体都顺了。
最后再分享一个小习惯：我每写完一版最大子矩阵代码，都会顺手测试三个样例——单个负数的 n=1 矩阵、单行矩阵、全负矩阵。这三个样例过了，基本的上考场底气就有了。祝你把该踩的坑都提前踩完，机试顺利。
