形式化题目

给定一个 $N \times N$（$N \leqslant 100$）的整数矩阵 $A$，元素取值在 $[-127, 127]$。要求选出一个非空的、行连续且列连续的子矩阵，使其元素和最大，即求

其中 $[i, j)$ 是行区间，$[l, r)$ 是列区间。子矩阵至少为 $1 \times 1$，所以答案一定存在，并且可能是负数（矩阵全为负时取最大的单个元素）。

以题面样例的 $4 \times 4$ 矩阵为例，最优子矩阵取第 $2 \sim 4$ 行、第 $1 \sim 2$ 列：

表中加粗的 $6$ 个格子构成答案子矩阵，元素和为 $9 + 2 + (-4) + 1 + (-1) + 8 = 15$。注意它与行、列都连续，这正是题目对"子矩阵"的要求。

正解

思路

一句话本质：枚举上下边界把二维压成一维，对"每列在该行区间内的和"跑一遍一维最大子段和（Kadane），$O(N^2)$ 个行区间就覆盖了所有子矩阵。

先看最朴素的做法：枚举矩形的四条边——上边界 $i$、下边界 $j$、左边界 $l$、右边界 $r$。用二维前缀和可以让"求一个矩形的和"变成 $O(1)$ 的四次加减：

但矩形本身有 $O(N^4)$ 个：$N = 100$ 时合法矩形数约 $\binom{101}{2}^2 \approx 2.5 \times 10^7$，纯枚举在 Python 下完全不可行。瓶颈在于把列的两个端点 $l$ 和 $r$ 也当成了独立的枚举对象，白白多花了一维。

关键观察是：行区间一旦固定，列方向就只剩一个一维问题。对固定的行区间 $[i, j)$，记第 $c$ 列在这几行里的和为

那么选择列区间 $[l, r)$ 得到的矩形和恰好是 $\sum_{c=l}^{r-1} S_c$（有限和可以交换次序）。于是"行区间 $[i, j)$ 下最好的列区间"就等于"数组 $S$ 中和最大的非空连续子段"，这是一维最大子段和，用 Kadane 一次线性扫描就能求出：

其中 $\text{acc}_c$ 表示"以第 $c$ 列为右端点的最大子段和"：要么从本列重新开始，要么把本列接在以上一列为右端点的最优子段后面。因为负的前缀只会拖后腿，所以这个"重新开始"的判断是充分的。

枚举 $O(N^2)$ 个行区间、每个跑一次 $O(N)$ 的 Kadane，总复杂度 $O(N^3)$，$N = 100$ 时约 $5 \times 10^5$ 次内层操作，比暴力低一个数量级。$S_c$ 不需要单独建表：用列前缀和 $P_c[t] = \sum_{x<t} A_{x,c}$ 一次减法即可得到 $S_c = P_c[j] - P_c[i]$。

用样例把所有行区间的结果都算出来，可以看到 $O(N^2)$ 个候选是被怎样枚举的：

表中每一行对应一个行区间：第二列是"把该行区间内每一列压成一个数"得到的列累加和，第三列是对这个一维数组跑 Kadane 的结果。全部 $10$ 个候选里第 $[2, 4]$ 行的 15 最大，与题面答案一致——这说明二维答案确实等价于"某个行区间的一维最大子段和"。

最后放大看获奖的那一行区间 $[2, 4]$，它是如何被一条线性扫描算出来的：

第 1 列 acc = 4 表示从它开始；第 2 列接到后面得 $4 + 11 = 15$，这是全程峰值；第 3 列的 $-10$ 把 acc 拖到 $5$，但仍是正的，所以第 4 列继续接上去得 $6$，不超过峰值。观察重点是 Kadane 用的是 $\max(S_c, \text{acc}+S_c)$ 而不是 $\max(0, \text{acc}+S_c)$：前者保证了"非空"，后者会在全负矩阵里错误地返回 0。

代码

best_segment 承担一维最大非空子段和；pref[c][t] 是第 $c$ 列前 $t$ 行之和，col[j] - col[i] 即行区间 $[i, j)$ 上该列的和；band 是惰性生成器，不额外开数组。

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
42
43
44
45#!/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 00:30
# update_at: 2026-09-30 00:30

import sys
from collections.abc import Iterable
from itertools import accumulate


def best_segment(nums: Iterable[int]) -> int:
    """一维最大非空子段和（Kadane），acc 表示"以当前元素结尾的最大和"。

    转移 max(x, acc + x)：前缀为负时从本元素重新开始，否则接在最优后缀后面。
    """
    return max(accumulate(nums, lambda acc, x: x if x > acc + x else acc + x))


def max_submatrix(rows: list[list[int]]) -> int:
    """非空子矩阵的最大元素和：枚举行区间，把列方向交给一维最大子段和。

    固定行区间 [i, j) 后每列之和是一个定值，列区间的最优选择只取决于这一维数组。
    """
    n = len(rows)
    # pref[c][t] 是第 c 列前 t 行之和，故列 c 在行区间 [i, j) 上的和 = pref[c][j] - pref[c][i]
    pref = [tuple(accumulate((0, *col))) for col in zip(*rows)]
    ans = pref[0][1]                                  # 至少取一格：用它兜住矩阵全为负数的情形
    for i in range(n):
        for j in range(i + 1, n + 1):                 # 行区间 [i, j) 保证非空
            band = (col[j] - col[i] for col in pref)  # 该行区间下每列的累加和
            ans = max(ans, best_segment(band))
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # N×N 的边长
    rows = [[next(data) for _ in range(n)] for _ in range(n)]
    print(max_submatrix(rows))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
53
54
55
56
57
58/**
 * 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:29
 * update_at: 2026-10-04 23:29
 */

#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 105;

// col_pref[c][t] 表示第 c 列前 t 行之和（列和行都从 1 开始编号）
// 于是第 c 列在行区间 [i, j) 上的和 = col_pref[c][j] - col_pref[c][i]
ll col_pref[MAXN][MAXN];

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

    int n;
    if (!(cin >> n)) return 0;

    for (int r = 1; r <= n; r++) {
        for (int c = 1; c <= n; c++) {
            ll x;
            cin >> x;
            col_pref[c][r] = col_pref[c][r - 1] + x;
        }
    }

    // 答案初值取一个真实单格和，保证矩阵全为负数时也能返回最大单格而不是 0
    ll ans = col_pref[1][1];

    // 枚举上下边界 i, j（行区间 [i, j) 非空），把二维压成一维
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            // 对该行区间下"每列的和"这一维数组跑 Kadane
            // acc 表示以当前列为右端点的最大非空子段和
            ll acc = col_pref[1][j] - col_pref[1][i];
            ll best = acc;
            for (int c = 2; c <= n; c++) {
                ll col_sum = col_pref[c][j] - col_pref[c][i];
                // 要么从本列重新开始，要么接在以上一列为右端点的最优子段后面
                acc = max(col_sum, acc + col_sum);
                best = max(best, acc);
            }
            ans = max(ans, best);
        }
    }

    cout << ans << endl;
    return 0;
}

复杂度

• 时间复杂度：$O(N^3)$。列前缀和 $O(N^2)$，枚举行区间 $O(N^2)$ 个、每个 Kadane $O(N)$。$N = 100$ 时约 $5.05 \times 10^5$ 次操作，对比暴力 $O(N^4)$ 的 $2.5 \times 10^7$ 低一个数量级；与 C++ 正解（枚举行区间 + 内层 Kadane）完全同阶。
• 空间复杂度：$O(N^2)$，存放列前缀和 $N \times (N+1)$ 个整数；每个行区间的 band 与 accumulate 都是惰性流，不建额外数组。实测峰值内存 16.0 MB（OJ 限 128 MB）。

总结

本题是"二维最大子矩阵"的模板题，核心动作只有一步：固定上下边界，把二维问题压成一维最大子段和。推导顺序是"暴力枚举四条边 $O(N^4)$ → 发现列的两个端点可以线性求出 → 行区间 $O(N^2)$ 次 Kadane $O(N)$，总计 $O(N^3)$"。两个容易翻车的细节：一是 ans 的初值不能取 0（矩阵全为负时答案应为最大单元素），代码里用 pref[0][1] 这个真实单格和兜底；二是 Kadane 的转移必须是 $\max(S_c, \text{acc} + S_c)$，一旦写成 $\max(0, \dots)$ 就破坏了"非空"约束。实测 10 个评测点全部与标准输出一致，最慢点不足 0.06 s、峰值内存 16.0 MB（OJ 限 1000 ms / 128 MB）。

图示解析

这张图串起本题从建模到得到答案的主线：

1
2
3
4
5
6N×N 矩阵 (N ≤ 100), 求非空子矩阵最大和
`- 朴素: 枚举上/下/左/右四条边, O(N⁴) 个矩形 (≈2.5×10⁷, Python 不可行)
   `- 瓶颈: 列的两个端点 l, r 被当成独立枚举对象, 多花一维
      `- 关键观察: 行区间 [i, j) 固定后, 列 c 的和 S_c = P_c[j] - P_c[i] 是定值
         `- 降维: 矩形和 = S 的连续子段和 → 一维最大子段和 (Kadane)
            `- 得到答案: O(N²) 个行区间 × O(N) 扫描 = O(N³)

先看每个节点代表的推理结论，再顺着分支检查它如何导向下一步：$N \leqslant 100$ 说明 $O(N^4)$ 过不了、$O(N^3)$ 是目标；"列和可预先算出"是把二维压成一维的理论依据；Kadane 负责在每个行区间里 $O(N)$ 取代 $O(N^2)$ 的列区间枚举；最终对全部行区间取 max 得到答案。