二维最大子矩阵和这个经典问题我在两组场景里都遇到过一次是刷算法题一次是业务中要在热力数据网格上找最大热点区域。大多数人的第一反应都是“枚举四条边界 二维前缀和加速求和”小矩阵上还能跑数据一旦到几百上千规模就彻底卡死。而枚举上下界 Kadane算法之所以能成为标准解法是因为它把“找子矩阵”拆成了两个层次先固定上、下两条行边界把二维矩阵压成一维的列和数组再在这个一维数组上跑 Kadane自动确定左、右边界。整体时间复杂度只有 O(m²n)空间 O(n)。这篇文章适合正在刷二维动态规划、准备算法面试或者需要在工程里做二维区间聚合的读者我会把从一维 Kadane 到二维坐标回溯的完整链路讲透并给出可直接复用的代码。1. 从一维到二维Kadane算法为什么能直接迁移1.1 一维Kadane算法不是“背模板”是动态规划最大连续子数组和Maximum Subarray是算法入门必刷题给定数组a找出一个非空连续子数组使其和最大。Kadane 算法的核心非常朴素——维护一个滚动变量cur它始终代表“以当前元素结尾的最大连续子数组和”。每扫到新元素a[i]只面临两个选择把a[i]接到前面那段连续区间后面cur a[i]放弃前面那段让a[i]重新作为起点a[i]于是状态转移就是一句话cur max(a[i], cur a[i])同时用ans记录历史所有cur的最大值扫完就得到答案。这个转移本质是动态规划设f[i]是以a[i]结尾的最大连续子数组和那么最优子结构就是“要么自己开头要么接在 f[i-1] 对应的区间后面”。这里的直觉值得多说一句如果cur已经是负数它作为“前缀”对后续元素只会拖后腿。比如你爬山前面一段净海拔已经是负的那后面想走高必然应该换起点而不是从更早的地方继续接。这也是“连续”这个约束下贪心与 DP 能同时成立的原因。很多资料把 Kadane 写成cur max(0, cur a[i])这其实是允许空子数组的版本全负数数组会返回 0。而二维最大子矩阵问题里题目几乎都要求非空子矩阵所以更稳妥的写法是cur max(a[i], cur a[i])。这个细节看起来小但全负矩阵的测试用例会立刻暴露问题后面第 3 节我专门展开。1.2 二维暴力解的空间到底有多大二维问题的定义是给定 m×n 矩阵每个元素有正有负求所有子矩阵中元素和的最大值。一个子矩阵由四条边界确定上边界top、下边界bottom、左边界left、右边界right。如果直接暴力枚举四条边界子矩阵总数是 O(m²n²) 种。就算提前构建二维前缀和把“求子矩阵和”这一步从 O(mn) 优化到 O(1)总复杂度仍然是 O(m²n²)。当 m n 100 时是 1e8 次操作勉强能忍到 m n 1000 就是 1e12任何语言都跑不动。如果不用二维前缀和每次求和全靠裸加复杂度直接是 O(m³n³)只能适配个位数规模的矩阵。为什么二维比一维难这么多一维的子区间只有左右两个端点二维的子矩阵却有四条边界组合数呈数量级爆炸。所以优化的方向必然只有一个减少需要显式枚举的边界数量。二维前缀和只优化了“求和”的常数没有减少边界组合所以它解决不了根本问题。1.3 固定行边界后列方向的连续区间问题标准解法只做了一件事只枚举top和bottom两条行边界然后把[top, bottom]这段行区间内每一列的元素累加成一个数得到长度 n 的一维数组colSumcolSum[j] mat[top][j] mat[top1][j] ... mat[bottom][j]此时问题变成了在colSum上找一个连续区间[left, right]使得区间和最大。因为上下边界已经固定任何left/right组合都唯一对应一个“上下边界恰好是 top/bottom”的子矩阵。而在一个一维数组上找最大连续区间和正是 Kadane 算法线性扫描能自动解决的事情。于是外层枚举上下边界的 O(m²) 次循环每次都调用一次 O(n) 的 Kadane总复杂度 O(m²n)。相比枚举四条边界的 O(m²n²)“左边、右边”这两维边界被压缩进了 Kadane 的线性扫描里。如果你面试时能把这个“为什么可以压缩维度”的逻辑讲清楚比单纯背下代码有价值得多。可以这样理解把矩阵想象成从上往下叠的一沓纸每固定一个上下层段就把这个层段在每一列的厚度叠成一条竖条然后在竖条上做“最大连续段”搜索。所谓最大子矩阵本质就是“在行方向上选一段层叠在列方向上选一段区间”。2. 枚举上下边界时的经典误区列和为什么要增量更新2.1 标准框架的伪代码标准流程可以用下面这段伪代码概括ans -inf for top in 0..m-1: colSum [0] * n # 每一轮 top 都要重置列和数组 for bottom in top..m-1: # 关键增量更新 colSum[j] mat[bottom][j] (j 0..n-1) # 在 colSum 上跑 Kadane更新 ans这里最容易被忽略也最值得展开的就是colSum的更新方式。当bottom从上一行下移到当前行时不需要重新计算top到bottom之间所有行的列和只需要把新进入行区间的这一行累加进colSum即可。因为上一次循环里的colSum已经表示top到bottom-1行的列和再叠加一行就精确变成了top到bottom行的列和。这个技巧之所以成立是因为我们的枚举顺序是从某个top开始把bottom依次向下扫行区间是“逐步扩张”的。后一个状态可以由前一个状态 O(n) 转移得到这就是最朴素的滚动累加思想。2.2 反模式一每轮重新累加行区间最容易写错、也最常见的低效写法是这种for top in range(m): for bottom in range(top, m): col_sum [0] * n for r in range(top, bottom 1): for j in range(n): col_sum[j] mat[r][j] # 又把 top..bottom 全扫一遍 kadane(col_sum)这个版本的问题在于每次bottom变化都要把top到bottom的整段行区间重新扫一遍来构建colSum。构建代价是 O((bottom - top 1) * n)把所有top/bottom组合加起来总复杂度是 O(m³n)。从 O(m²n) 退化成 O(m³n)听起来只多了一个 m但 m 1000 时就是 1e12 和 1e9 的区别本质上是“可跑”与“不可跑”的区别。2.3 反模式二二维前缀和逐列差分还有人会用列方向的前缀和来算col_sum[j] pre[bottom 1][j] - pre[top][j] # 每轮做 n 次差分严格说这个写法复杂度没有退化也是 O(m²n)。但它有两个代价需要额外维护一个 O(mn) 的二维前缀和数组每轮循环都必须把 n 列都做一次减法常数上比“只加新一行”的增量更新更大。如果你的矩阵是逐行读入的我更推荐增量更新代码更短、常数更小、不需要额外空间。除非你的输入不是按行顺序给的或者你确实需要频繁随机查询任意行区间的列和那种场景二维前缀和才有不可替代的优势。2.4 正确性与复杂度分析简单证明一下增量更新的正确性。记S(top, bottom, j)为第 j 列从第 top 行到第 bottom 行的元素和。外层固定 top 后初始colSum全 0当 bottom 从 b-1 变成 b 时S(top, b, j) S(top, b-1, j) mat[b][j]所以循环中的colSum[j] mat[bottom][j]这句操作维护的正是“当前 top 行到底行之间的第 j 列和”。bottom 每取一个值colSum 都是精确的 [top, bottom] 列和再跑 Kadane得到的就严格等于“上下边界分别为 top 和 bottom 时最优子矩阵的和”。复杂度账很好算外层 top 有 O(m) 种内层 bottom 平均 O(m/2) 种每次 bottom 循环里“累加新行”O(n) “Kadane 扫描”O(n)。总复杂度 O(m²n)空间只是一个长度 n 的colSum数组O(n)。注意如果矩阵是“高瘦型”即 n 远小于 m那么更优策略是反过来枚举左/右边界的组合对行做 rowSum 增量更新Kadane 在行方向上扫描复杂度变成 O(n²m)。核心原则是不要盲目固定方向看哪种枚举维度的组合数更小。这一点第 5 节我再补充。3. 完整实现与手动推演从Python到C的落地细节3.1 Python实现与初始化的坑先给一个最简的可运行版本只返回最大和def max_submatrix_sum(mat): m, n len(mat), len(mat[0]) if m 0 or n 0: return 0 ans float(-inf) for top in range(m): col_sum [0] * n for bottom in range(top, m): # 增量更新列和 for j in range(n): col_sum[j] mat[bottom][j] # 一维 Kadane非空子数组版本 cur 0 for val in col_sum: cur max(val, cur val) if cur ans: ans cur return ans初始化这里的几个细节建议死记ans用float(-inf)初始化。如果题目允许返回空矩阵即答案为 0改成ans 0也行但绝大多数“最大子矩阵和”题目要求子矩阵非空全负矩阵时正确答案应该是最大那个单一元素而不是 0。内层 Kadane 里cur初始化为 0 没有任何问题。因为第一次遇到元素val时cur max(val, 0 val) val起点自动从第一个元素开始了。千万不要把内层写成cur max(0, cur val)。这个写法返回的是“允许空区间”的最大和全负矩阵会让你得到 0而不是真实的负值最大元素。3.2 一个3×3矩阵手动走一遍理论说再多不如手算一个例子。用下面这个 3×3 矩阵[ 1, -2, 3] [ 4, -5, 6] [-7, 8, 9]把每一种 top/bottom 组合对应的 colSum 和 Kadane 结果列出来topbottomcolSumKadane最大和00[1, -2, 3]301[5, -7, 9]902[-2, 1, 18]1911[4, -5, 6]612[-3, 3, 15]1822[-7, 8, 9]17以 top0、bottom2 为例colSum [-2, 1, 18]。Kadane 扫描过程val -2cur max(-2, 0 (-2)) -2ans -2val 1cur max(1, -2 1) 1ans 1val 18cur max(18, 1 18) 19ans 19最终全局最大值是 19对应子矩阵是第 0~2 行、第 1~2 列-2, 3 -5, 6 8, 9手动验算(-23) (-56) (89) 1 1 17 19正确。这个推演也能解释一个常见困惑最大子矩阵不一定是“从某一行开始到某一行结束”时最大的那个而是在多个 top/bottom 组合的 Kadane 结果中取历史最大值。所以每轮循环都必须持续和全局 ans 比较。3.3 C实现、long long与浮点扩展竞赛或工程里用 C 时代码长这样#include vector #include algorithm #include climits using namespace std; long long maxSubMatrix(const vectorvectorlong long mat) { int m mat.size(); if (m 0) return 0; int n mat[0].size(); long long ans LLONG_MIN; for (int top 0; top m; top) { vectorlong long colSum(n, 0); for (int bottom top; bottom m; bottom) { for (int j 0; j n; j) { colSum[j] mat[bottom][j]; } long long cur 0; for (int j 0; j n; j) { cur max(colSum[j], cur colSum[j]); ans max(ans, cur); } } } return ans; }两个工程经验矩阵权值和上限不明时colSum、cur、ans一律用long long。用 int 的话cur colSum[j]在边界数据下很容易溢出而且这个问题通常要到测试大样例才会暴露。如果矩阵元素是浮点类型图像处理、信号处理很常见把long long换成double即可Kadane 的贪心逻辑完全一致。4. 从“求最大和”到“框出子矩阵”坐标回溯实战4.1 一维Kadane记录左右端点很多业务场景不能只返回一个最大和还得告诉下游“最大热点区域到底在哪”。这时候只维护cur和ans不够需要额外记录子数组的左右端点。关键技巧是维护一个“临时起点”变量def kadane_with_index(arr): best float(-inf) cur 0 l r 0 tmp_l 0 for i, val in enumerate(arr): if cur val val: cur cur val else: cur val tmp_l i if cur best: best cur l, r tmp_l, i return best, l, r这里的tmp_l只在“决定放弃之前的区间从当前元素重新开始”时才更新为当前下标。如果cur接上了前面的区间临时起点不用变。只有当cur刷新了best才把正式的端点l, r更新为(tmp_l, i)。4.2 合成二维坐标的完整代码把带坐标的一维 Kadane 嵌进 top/bottom 循环就可以同时拿到最大和与完整子矩阵边界def max_submatrix_with_position(mat): m, n len(mat), len(mat[0]) ans float(-inf) final_top final_left final_bottom final_right 0 for top in range(m): col_sum [0] * n for bottom in range(top, m): for j in range(n): col_sum[j] mat[bottom][j] best, left, right kadane_with_index(col_sum) if best ans: ans best final_top, final_bottom top, bottom final_left, final_right left, right return ans, (final_top, final_left, final_bottom, final_right)final_top和final_bottom来自外层枚举final_left和final_right来自 Kadane 返回的左右端点四者组合起来就是一个完整子矩阵的四个边界。调用方拿到(top, left, bottom, right)之后可以很方便地切片原矩阵做可视化或进一步计算。4.3 多个最优解的场景化取舍当矩阵里有多个子矩阵同时达到最大和时上面代码默认返回“第一个被扫描到”的最优解因为更新条件是严格大于best ans。这个行为通常够用但有些场景会有额外偏好如果希望返回“最后一个”最优解把改成即可如果希望返回“区间最长”的解Kadane 内部的更新条件需要增加长度比较cur best或者cur best and i - tmp_l r - l时更新如果希望返回“上下边界跨度最小”或“面积最小”的解则要在外层 top/bottom 循环里增加判断。需要特别提醒的是这些额外规则必须在 Kadane 内部的端点维护阶段就处理因为端点信息只在 Kadane 内部可见。等返回外层再补救很容易写出重复扫描数组的代码。5. 边界情况、复杂度对比与进阶变体5.1 必测的六类边界用例写完标准解法后建议至少用下面六类用例回归测试能挡掉 90% 的边界 bug用例类型示例期望结果说明单元素矩阵[[-5]]-5立刻暴露“全负返回0”的问题全负矩阵[[-1,-2],[-3,-4]]-1非空子矩阵要求单行矩阵[3, -1, 4]6退化为1D Kadane单列矩阵[[1],[2],[-3]]3退化为1D Kadane全正矩阵[[1,2],[3,4]]10答案是全矩阵之和含0矩阵[[0,-5],[0,3]]30元素参与取最大值尤其注意的是[[-5]]和[[-1,-2],[-3,-4]]这两个用例。很多网上流传的题解在这个用例上会返回 0就是因为内层 Kadane 误用了cur max(0, cur val)。不是所有场景都要求非空子矩阵所以写代码前一定要先和需求方确认空矩阵算不算一个合法“子矩阵”。5.2 枚举方向的选择与复杂度对照表把几种典型方法放在一起看复杂度高低一目了然方法时间复杂度空间复杂度mn1000 时的量级暴力枚举 裸求和O(m³n³)O(1)1e18完全不可行暴力枚举 二维前缀和O(m²n²)O(mn)1e12不可行枚举上下边界 KadaneO(m²n)O(n)1e9常数优化后可跑枚举左右边界 KadaneO(n²m)O(m)1e9取决于m/n工程上的朴素经验是“谁短枚举谁”。严谨一点比较m²n和n²m的大小约掉公因子mn后等价于比较m和n。比如 m 2000、n 20 时枚举左右边界是 O(20² × 2000) 8e5比枚举上下边界 O(2000² × 20) 8e7 快 100 倍。这种常量级优化在大型网格数据处理时效果非常明显。5.3 进阶面积不超过K的矩形最大和LeetCode 363“矩形区域不超过 K 的最大数值和”是标准解法最常见的变体。思路同样先枚举上下边界拿到 colSum但目标不再是“最大连续和”而是“最大但不超过 K 的连续和”。Kadane 的贪心在这个限制下会失效。原因很简单Kadane 每一步追求的是“当前局部最优”但带 K 上限时一个暂时的“次优前缀和”可能反而能组合出满足 K 限制的更优答案。正确做法是回到前缀和 有序集合固定 top/bottom 得到 colSum 后求前缀和数组 prefix其中prefix[i] sum(colSum[0..i-1])遍历右端点 r i 时需要找到已经出现过的prefix[l]l i满足prefix[l] prefix[i] - K且尽可能小这样prefix[i] - prefix[l]就尽可能接近 K用有序集合维护已扫描的prefix通过lower_bound(prefix[i] - K)快速查询。整体复杂度 O(m² n log n)。这个变体把“Kadane 的贪心”与“前缀和 二分查找”合在一起非常适合作为标准解法的延伸练习。5.4 进阶最大平均子矩阵、三维甚至更高维如果换成“最大平均子矩阵”问题要找到平均值最大的矩形区域可以二分答案 mid把矩阵每个元素都减去 mid然后跑一遍本文的标准解法求最大子矩阵和。如果最大和 ≥ 0说明存在平均值 ≥ mid 的矩形。总复杂度 O(m² n log(精度))。这个思路在图像处理找最亮区域、信号处理找能量密度最高的窗口时都有应用。更高维的“最大子长方体”问题原理完全一致先枚举 z 方向的两层边界把三维长方体压成二维矩阵再在这个二维矩阵上用枚举上下界 Kadane 继续压成一维最后 Kadane 收尾。本质就是“一层一层向下压维”每一层都借用一次枚举边界 线性扫描的组合维数越高越是重复套用这个模式。最后分享一个我自己的习惯拿到二维最大子矩阵相关的题永远先画一张“上下边界固定、列和数组”的抽象图把思路落在纸上再写代码。因为这个解法真正的难点不在 Kadane——它本身就是一维经典算法——而在枚举上下边界时能不能看清“列和是随着 bottom 滚动更新的”。只要你的代码没有在 bottom 循环里重新累加多行数据基本很难写错。编码完之后记得一定跑一遍单元素、单行、单列、全负这几个测试用例能挡掉大部分边界 bug。这套“枚举上下界 Kadane”的模式值得你从今天开始纳入自己的算法工具箱。
二维最大子矩阵和这个经典问题我在两组场景里都遇到过一次是刷算法题一次是业务中要在热力数据网格上找最大热点区域。大多数人的第一反应都是“枚举四条边界 二维前缀和加速求和”小矩阵上还能跑数据一旦到几百上千规模就彻底卡死。而枚举上下界 Kadane算法之所以能成为标准解法是因为它把“找子矩阵”拆成了两个层次先固定上、下两条行边界把二维矩阵压成一维的列和数组再在这个一维数组上跑 Kadane自动确定左、右边界。整体时间复杂度只有 O(m²n)空间 O(n)。这篇文章适合正在刷二维动态规划、准备算法面试或者需要在工程里做二维区间聚合的读者我会把从一维 Kadane 到二维坐标回溯的完整链路讲透并给出可直接复用的代码。1. 从一维到二维Kadane算法为什么能直接迁移1.1 一维Kadane算法不是“背模板”是动态规划最大连续子数组和Maximum Subarray是算法入门必刷题给定数组a找出一个非空连续子数组使其和最大。Kadane 算法的核心非常朴素——维护一个滚动变量cur它始终代表“以当前元素结尾的最大连续子数组和”。每扫到新元素a[i]只面临两个选择把a[i]接到前面那段连续区间后面cur a[i]放弃前面那段让a[i]重新作为起点a[i]于是状态转移就是一句话cur max(a[i], cur a[i])同时用ans记录历史所有cur的最大值扫完就得到答案。这个转移本质是动态规划设f[i]是以a[i]结尾的最大连续子数组和那么最优子结构就是“要么自己开头要么接在 f[i-1] 对应的区间后面”。这里的直觉值得多说一句如果cur已经是负数它作为“前缀”对后续元素只会拖后腿。比如你爬山前面一段净海拔已经是负的那后面想走高必然应该换起点而不是从更早的地方继续接。这也是“连续”这个约束下贪心与 DP 能同时成立的原因。很多资料把 Kadane 写成cur max(0, cur a[i])这其实是允许空子数组的版本全负数数组会返回 0。而二维最大子矩阵问题里题目几乎都要求非空子矩阵所以更稳妥的写法是cur max(a[i], cur a[i])。这个细节看起来小但全负矩阵的测试用例会立刻暴露问题后面第 3 节我专门展开。1.2 二维暴力解的空间到底有多大二维问题的定义是给定 m×n 矩阵每个元素有正有负求所有子矩阵中元素和的最大值。一个子矩阵由四条边界确定上边界top、下边界bottom、左边界left、右边界right。如果直接暴力枚举四条边界子矩阵总数是 O(m²n²) 种。就算提前构建二维前缀和把“求子矩阵和”这一步从 O(mn) 优化到 O(1)总复杂度仍然是 O(m²n²)。当 m n 100 时是 1e8 次操作勉强能忍到 m n 1000 就是 1e12任何语言都跑不动。如果不用二维前缀和每次求和全靠裸加复杂度直接是 O(m³n³)只能适配个位数规模的矩阵。为什么二维比一维难这么多一维的子区间只有左右两个端点二维的子矩阵却有四条边界组合数呈数量级爆炸。所以优化的方向必然只有一个减少需要显式枚举的边界数量。二维前缀和只优化了“求和”的常数没有减少边界组合所以它解决不了根本问题。1.3 固定行边界后列方向的连续区间问题标准解法只做了一件事只枚举top和bottom两条行边界然后把[top, bottom]这段行区间内每一列的元素累加成一个数得到长度 n 的一维数组colSumcolSum[j] mat[top][j] mat[top1][j] ... mat[bottom][j]此时问题变成了在colSum上找一个连续区间[left, right]使得区间和最大。因为上下边界已经固定任何left/right组合都唯一对应一个“上下边界恰好是 top/bottom”的子矩阵。而在一个一维数组上找最大连续区间和正是 Kadane 算法线性扫描能自动解决的事情。于是外层枚举上下边界的 O(m²) 次循环每次都调用一次 O(n) 的 Kadane总复杂度 O(m²n)。相比枚举四条边界的 O(m²n²)“左边、右边”这两维边界被压缩进了 Kadane 的线性扫描里。如果你面试时能把这个“为什么可以压缩维度”的逻辑讲清楚比单纯背下代码有价值得多。可以这样理解把矩阵想象成从上往下叠的一沓纸每固定一个上下层段就把这个层段在每一列的厚度叠成一条竖条然后在竖条上做“最大连续段”搜索。所谓最大子矩阵本质就是“在行方向上选一段层叠在列方向上选一段区间”。2. 枚举上下边界时的经典误区列和为什么要增量更新2.1 标准框架的伪代码标准流程可以用下面这段伪代码概括ans -inf for top in 0..m-1: colSum [0] * n # 每一轮 top 都要重置列和数组 for bottom in top..m-1: # 关键增量更新 colSum[j] mat[bottom][j] (j 0..n-1) # 在 colSum 上跑 Kadane更新 ans这里最容易被忽略也最值得展开的就是colSum的更新方式。当bottom从上一行下移到当前行时不需要重新计算top到bottom之间所有行的列和只需要把新进入行区间的这一行累加进colSum即可。因为上一次循环里的colSum已经表示top到bottom-1行的列和再叠加一行就精确变成了top到bottom行的列和。这个技巧之所以成立是因为我们的枚举顺序是从某个top开始把bottom依次向下扫行区间是“逐步扩张”的。后一个状态可以由前一个状态 O(n) 转移得到这就是最朴素的滚动累加思想。2.2 反模式一每轮重新累加行区间最容易写错、也最常见的低效写法是这种for top in range(m): for bottom in range(top, m): col_sum [0] * n for r in range(top, bottom 1): for j in range(n): col_sum[j] mat[r][j] # 又把 top..bottom 全扫一遍 kadane(col_sum)这个版本的问题在于每次bottom变化都要把top到bottom的整段行区间重新扫一遍来构建colSum。构建代价是 O((bottom - top 1) * n)把所有top/bottom组合加起来总复杂度是 O(m³n)。从 O(m²n) 退化成 O(m³n)听起来只多了一个 m但 m 1000 时就是 1e12 和 1e9 的区别本质上是“可跑”与“不可跑”的区别。2.3 反模式二二维前缀和逐列差分还有人会用列方向的前缀和来算col_sum[j] pre[bottom 1][j] - pre[top][j] # 每轮做 n 次差分严格说这个写法复杂度没有退化也是 O(m²n)。但它有两个代价需要额外维护一个 O(mn) 的二维前缀和数组每轮循环都必须把 n 列都做一次减法常数上比“只加新一行”的增量更新更大。如果你的矩阵是逐行读入的我更推荐增量更新代码更短、常数更小、不需要额外空间。除非你的输入不是按行顺序给的或者你确实需要频繁随机查询任意行区间的列和那种场景二维前缀和才有不可替代的优势。2.4 正确性与复杂度分析简单证明一下增量更新的正确性。记S(top, bottom, j)为第 j 列从第 top 行到第 bottom 行的元素和。外层固定 top 后初始colSum全 0当 bottom 从 b-1 变成 b 时S(top, b, j) S(top, b-1, j) mat[b][j]所以循环中的colSum[j] mat[bottom][j]这句操作维护的正是“当前 top 行到底行之间的第 j 列和”。bottom 每取一个值colSum 都是精确的 [top, bottom] 列和再跑 Kadane得到的就严格等于“上下边界分别为 top 和 bottom 时最优子矩阵的和”。复杂度账很好算外层 top 有 O(m) 种内层 bottom 平均 O(m/2) 种每次 bottom 循环里“累加新行”O(n) “Kadane 扫描”O(n)。总复杂度 O(m²n)空间只是一个长度 n 的colSum数组O(n)。注意如果矩阵是“高瘦型”即 n 远小于 m那么更优策略是反过来枚举左/右边界的组合对行做 rowSum 增量更新Kadane 在行方向上扫描复杂度变成 O(n²m)。核心原则是不要盲目固定方向看哪种枚举维度的组合数更小。这一点第 5 节我再补充。3. 完整实现与手动推演从Python到C的落地细节3.1 Python实现与初始化的坑先给一个最简的可运行版本只返回最大和def max_submatrix_sum(mat): m, n len(mat), len(mat[0]) if m 0 or n 0: return 0 ans float(-inf) for top in range(m): col_sum [0] * n for bottom in range(top, m): # 增量更新列和 for j in range(n): col_sum[j] mat[bottom][j] # 一维 Kadane非空子数组版本 cur 0 for val in col_sum: cur max(val, cur val) if cur ans: ans cur return ans初始化这里的几个细节建议死记ans用float(-inf)初始化。如果题目允许返回空矩阵即答案为 0改成ans 0也行但绝大多数“最大子矩阵和”题目要求子矩阵非空全负矩阵时正确答案应该是最大那个单一元素而不是 0。内层 Kadane 里cur初始化为 0 没有任何问题。因为第一次遇到元素val时cur max(val, 0 val) val起点自动从第一个元素开始了。千万不要把内层写成cur max(0, cur val)。这个写法返回的是“允许空区间”的最大和全负矩阵会让你得到 0而不是真实的负值最大元素。3.2 一个3×3矩阵手动走一遍理论说再多不如手算一个例子。用下面这个 3×3 矩阵[ 1, -2, 3] [ 4, -5, 6] [-7, 8, 9]把每一种 top/bottom 组合对应的 colSum 和 Kadane 结果列出来topbottomcolSumKadane最大和00[1, -2, 3]301[5, -7, 9]902[-2, 1, 18]1911[4, -5, 6]612[-3, 3, 15]1822[-7, 8, 9]17以 top0、bottom2 为例colSum [-2, 1, 18]。Kadane 扫描过程val -2cur max(-2, 0 (-2)) -2ans -2val 1cur max(1, -2 1) 1ans 1val 18cur max(18, 1 18) 19ans 19最终全局最大值是 19对应子矩阵是第 0~2 行、第 1~2 列-2, 3 -5, 6 8, 9手动验算(-23) (-56) (89) 1 1 17 19正确。这个推演也能解释一个常见困惑最大子矩阵不一定是“从某一行开始到某一行结束”时最大的那个而是在多个 top/bottom 组合的 Kadane 结果中取历史最大值。所以每轮循环都必须持续和全局 ans 比较。3.3 C实现、long long与浮点扩展竞赛或工程里用 C 时代码长这样#include vector #include algorithm #include climits using namespace std; long long maxSubMatrix(const vectorvectorlong long mat) { int m mat.size(); if (m 0) return 0; int n mat[0].size(); long long ans LLONG_MIN; for (int top 0; top m; top) { vectorlong long colSum(n, 0); for (int bottom top; bottom m; bottom) { for (int j 0; j n; j) { colSum[j] mat[bottom][j]; } long long cur 0; for (int j 0; j n; j) { cur max(colSum[j], cur colSum[j]); ans max(ans, cur); } } } return ans; }两个工程经验矩阵权值和上限不明时colSum、cur、ans一律用long long。用 int 的话cur colSum[j]在边界数据下很容易溢出而且这个问题通常要到测试大样例才会暴露。如果矩阵元素是浮点类型图像处理、信号处理很常见把long long换成double即可Kadane 的贪心逻辑完全一致。4. 从“求最大和”到“框出子矩阵”坐标回溯实战4.1 一维Kadane记录左右端点很多业务场景不能只返回一个最大和还得告诉下游“最大热点区域到底在哪”。这时候只维护cur和ans不够需要额外记录子数组的左右端点。关键技巧是维护一个“临时起点”变量def kadane_with_index(arr): best float(-inf) cur 0 l r 0 tmp_l 0 for i, val in enumerate(arr): if cur val val: cur cur val else: cur val tmp_l i if cur best: best cur l, r tmp_l, i return best, l, r这里的tmp_l只在“决定放弃之前的区间从当前元素重新开始”时才更新为当前下标。如果cur接上了前面的区间临时起点不用变。只有当cur刷新了best才把正式的端点l, r更新为(tmp_l, i)。4.2 合成二维坐标的完整代码把带坐标的一维 Kadane 嵌进 top/bottom 循环就可以同时拿到最大和与完整子矩阵边界def max_submatrix_with_position(mat): m, n len(mat), len(mat[0]) ans float(-inf) final_top final_left final_bottom final_right 0 for top in range(m): col_sum [0] * n for bottom in range(top, m): for j in range(n): col_sum[j] mat[bottom][j] best, left, right kadane_with_index(col_sum) if best ans: ans best final_top, final_bottom top, bottom final_left, final_right left, right return ans, (final_top, final_left, final_bottom, final_right)final_top和final_bottom来自外层枚举final_left和final_right来自 Kadane 返回的左右端点四者组合起来就是一个完整子矩阵的四个边界。调用方拿到(top, left, bottom, right)之后可以很方便地切片原矩阵做可视化或进一步计算。4.3 多个最优解的场景化取舍当矩阵里有多个子矩阵同时达到最大和时上面代码默认返回“第一个被扫描到”的最优解因为更新条件是严格大于best ans。这个行为通常够用但有些场景会有额外偏好如果希望返回“最后一个”最优解把改成即可如果希望返回“区间最长”的解Kadane 内部的更新条件需要增加长度比较cur best或者cur best and i - tmp_l r - l时更新如果希望返回“上下边界跨度最小”或“面积最小”的解则要在外层 top/bottom 循环里增加判断。需要特别提醒的是这些额外规则必须在 Kadane 内部的端点维护阶段就处理因为端点信息只在 Kadane 内部可见。等返回外层再补救很容易写出重复扫描数组的代码。5. 边界情况、复杂度对比与进阶变体5.1 必测的六类边界用例写完标准解法后建议至少用下面六类用例回归测试能挡掉 90% 的边界 bug用例类型示例期望结果说明单元素矩阵[[-5]]-5立刻暴露“全负返回0”的问题全负矩阵[[-1,-2],[-3,-4]]-1非空子矩阵要求单行矩阵[3, -1, 4]6退化为1D Kadane单列矩阵[[1],[2],[-3]]3退化为1D Kadane全正矩阵[[1,2],[3,4]]10答案是全矩阵之和含0矩阵[[0,-5],[0,3]]30元素参与取最大值尤其注意的是[[-5]]和[[-1,-2],[-3,-4]]这两个用例。很多网上流传的题解在这个用例上会返回 0就是因为内层 Kadane 误用了cur max(0, cur val)。不是所有场景都要求非空子矩阵所以写代码前一定要先和需求方确认空矩阵算不算一个合法“子矩阵”。5.2 枚举方向的选择与复杂度对照表把几种典型方法放在一起看复杂度高低一目了然方法时间复杂度空间复杂度mn1000 时的量级暴力枚举 裸求和O(m³n³)O(1)1e18完全不可行暴力枚举 二维前缀和O(m²n²)O(mn)1e12不可行枚举上下边界 KadaneO(m²n)O(n)1e9常数优化后可跑枚举左右边界 KadaneO(n²m)O(m)1e9取决于m/n工程上的朴素经验是“谁短枚举谁”。严谨一点比较m²n和n²m的大小约掉公因子mn后等价于比较m和n。比如 m 2000、n 20 时枚举左右边界是 O(20² × 2000) 8e5比枚举上下边界 O(2000² × 20) 8e7 快 100 倍。这种常量级优化在大型网格数据处理时效果非常明显。5.3 进阶面积不超过K的矩形最大和LeetCode 363“矩形区域不超过 K 的最大数值和”是标准解法最常见的变体。思路同样先枚举上下边界拿到 colSum但目标不再是“最大连续和”而是“最大但不超过 K 的连续和”。Kadane 的贪心在这个限制下会失效。原因很简单Kadane 每一步追求的是“当前局部最优”但带 K 上限时一个暂时的“次优前缀和”可能反而能组合出满足 K 限制的更优答案。正确做法是回到前缀和 有序集合固定 top/bottom 得到 colSum 后求前缀和数组 prefix其中prefix[i] sum(colSum[0..i-1])遍历右端点 r i 时需要找到已经出现过的prefix[l]l i满足prefix[l] prefix[i] - K且尽可能小这样prefix[i] - prefix[l]就尽可能接近 K用有序集合维护已扫描的prefix通过lower_bound(prefix[i] - K)快速查询。整体复杂度 O(m² n log n)。这个变体把“Kadane 的贪心”与“前缀和 二分查找”合在一起非常适合作为标准解法的延伸练习。5.4 进阶最大平均子矩阵、三维甚至更高维如果换成“最大平均子矩阵”问题要找到平均值最大的矩形区域可以二分答案 mid把矩阵每个元素都减去 mid然后跑一遍本文的标准解法求最大子矩阵和。如果最大和 ≥ 0说明存在平均值 ≥ mid 的矩形。总复杂度 O(m² n log(精度))。这个思路在图像处理找最亮区域、信号处理找能量密度最高的窗口时都有应用。更高维的“最大子长方体”问题原理完全一致先枚举 z 方向的两层边界把三维长方体压成二维矩阵再在这个二维矩阵上用枚举上下界 Kadane 继续压成一维最后 Kadane 收尾。本质就是“一层一层向下压维”每一层都借用一次枚举边界 线性扫描的组合维数越高越是重复套用这个模式。最后分享一个我自己的习惯拿到二维最大子矩阵相关的题永远先画一张“上下边界固定、列和数组”的抽象图把思路落在纸上再写代码。因为这个解法真正的难点不在 Kadane——它本身就是一维经典算法——而在枚举上下边界时能不能看清“列和是随着 bottom 滚动更新的”。只要你的代码没有在 bottom 循环里重新累加多行数据基本很难写错。编码完之后记得一定跑一遍单元素、单行、单列、全负这几个测试用例能挡掉大部分边界 bug。这套“枚举上下界 Kadane”的模式值得你从今天开始纳入自己的算法工具箱。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
