最大子矩阵

形式化题目

给定一个 $N \times N$ 的整数矩阵 $A$ 。要求选出一个非空的连续子矩阵（行区间、列区间均连续），使其所有元素之和最大。

形式化地，求

\max_{0 \leqslant top \leqslant bottom < N}\ \max_{0 \leqslant l \leqslant r < N}\ \sum_{i=top}^{bottom}\sum_{j=l}^{r} A_{i,j}

其中至少选取一个元素。

样例

下面表格中加粗格子组成了样例的最大子矩阵（第 1~3 行、第 1~2 列），其和为 $15$ 。

0	1	2	3
0	-2	-7	0
9	2	-6	2
-4	1	-4	1
-1	8	0	-2

正解

思路

二维最大子矩阵可以从一维最大子段和扩展而来。

固定子矩阵的上边界 $top$ 和下边界 $bottom$ ，把这两行之间的每一列从上到下求和，得到一个长度为 $N$ 的一维数组 $col$ 。
此时任意连续列区间 $[l, r]$ 对应的子矩阵和，恰好等于 $col$ 中子段 $col[l..r]$ 的和。
因此问题转化为求该一维数组的最大子段和，可用 Kadane 算法在 $O(N)$ 时间内完成。
遍历所有 $top \leqslant bottom$ 的上下边界组合，全局最大的结果即为答案。

列压缩示意图

以样例为例，当 $top = 1$ 、 $bottom = 3$ 时，把第 1 到第 3 行按列相加：

\begin{aligned} col &= (9 + (-4) + (-1),\ 2 + 1 + 8,\ -6 + (-4) + 0,\ 2 + 1 + (-2)) \\ &= (4, 11, -10, 1) \end{aligned}

对该 $col$ 跑最大子段和，最优取前两列，得到 $4 + 11 = 15$ ，对应子矩阵

\begin{bmatrix} 9 & 2 \\ -4 & 1 \\ -1 & 8 \end{bmatrix}

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:03
# update_at: 2026-09-30 03:03

import sys


def max_subarray(arr: list[int]) -> int:
    """一维最大子段和：Kadane。"""
    best = cur = arr[0]
    for x in arr[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    n = next(it)
    a = [[next(it) for _ in range(n)] for _ in range(n)]  # n x n 矩阵

    ans = a[0][0]  # 至少选一个元素
    col = [0] * n
    for top in range(n):               # 枚举子矩阵上边界
        col = [0] * n                   # 列前缀和归零
        for bottom in range(top, n):     # 枚举子矩阵下边界
            for c in range(n):
                col[c] += a[bottom][c]  # 把第 bottom 行加入每一列的累加和
            ans = max(ans, max_subarray(col))  # 当前条带内的最大子段和

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 23:49
 * update_at: 2026-10-04 23:49
 */
#include <iostream>
#include <algorithm>

typedef long long ll;

const ll MAXN = 105; // 题目为 N x N 矩阵，N 一般不超过 100，留一点余量

ll n;
ll a[MAXN][MAXN]; // 原始矩阵
ll col[MAXN];     // 枚举上下边界时，每一列在 [top, bottom] 内的累加和

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n;
    for (ll i = 0; i < n; ++i)
        for (ll j = 0; j < n; ++j)
            std::cin >> a[i][j];

    ll ans = a[0][0]; // 答案初始化为某个元素，保证子矩阵非空

    // 枚举子矩阵的上边界 top
    for (ll top = 0; top < n; ++top) {
        for (ll j = 0; j < n; ++j) col[j] = 0; // 每换一个上边界，列和清零

        // 枚举子矩阵的下边界 bottom，同时把第 bottom 行累加进列和
        for (ll bottom = top; bottom < n; ++bottom) {
            for (ll j = 0; j < n; ++j)
                col[j] += a[bottom][j];

            // 对一维数组 col 做 Kadane 求最大子段和
            ll cur = col[0];
            ll best = col[0];
            for (ll j = 1; j < n; ++j) {
                cur = std::max(col[j], cur + col[j]);
                best = std::max(best, cur);
            }
            ans = std::max(ans, best);
        }
    }

    std::cout << ans << "\n";
    return 0;
}

复杂度

时间复杂度：枚举上边界 $O(N)$ 、枚举下边界 $O(N)$ 、列压缩 $O(N)$ 、Kadane $O(N)$ ，总复杂度为 $O(N^3)$ 。
空间复杂度：存储矩阵 $O(N^2)$ ，列压缩数组 $O(N)$ ，总复杂度为 $O(N^2)$ 。

总结

本题的核心观察是：二维子矩阵的搜索可以拆成“枚举行区间”与“一维最大子段和”两个子问题。通过列压缩把每一对上下边界对应成一个一维数组，再用 Kadane 算法在 $O(N)$ 时间内求出最佳列区间，最终得到 $O(N^3)$ 的整体解法。实现时需注意 Kadane 初始值必须取数组第一个元素，以保证子段（也就是子矩阵）非空。

目录

形式化题目

正解

思路

列压缩示意图

代码

复杂度

总结