最大加权矩形

题意

在 $n\times n$ 的整数矩阵中选择一个非空子矩形，使矩形内所有元素之和最大。

一个子矩形必须选择连续的若干行和连续的若干列。例如样例中的最优矩形选择第 $2$ 到第 $4$ 行、第 $1$ 到第 $2$ 列，元素和为 $15$ 。

思路

从最直接的枚举开始

一个矩形由上、下、左、右四条边确定。最直接的做法是枚举这四条边，再逐格累加矩形中的元素：

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/**
 * 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-07-16 17:48
 * update_at: 2026-07-19 17:39
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 125;

int n;
int matrix[MAX_N][MAX_N];

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> matrix[i][j];
        }
    }

    int answer = INT_MIN;

    // 直接枚举矩形的四条边，再逐格计算矩形和，只适合小数据。
    for (int top = 1; top <= n; top++) {
        for (int bottom = top; bottom <= n; bottom++) {
            for (int left = 1; left <= n; left++) {
                for (int right = left; right <= n; right++) {
                    int sum = 0;
                    for (int i = top; i <= bottom; i++) {
                        for (int j = left; j <= right; j++) {
                            sum += matrix[i][j];
                        }
                    }
                    answer = max(answer, sum);
                }
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

四条边有 $O(n^4)$ 种组合，每次逐格求和还需要 $O(n^2)$ ，因此这个暴力最坏是 $O(n^6)$ ，只适合小数据验证。

真正需要优化的问题是：怎样少枚举一些边？

固定上下边界，把矩形压成一维

先固定矩形的上边界 top 和下边界 bottom。这时矩形要选哪些行已经确定，只剩下左、右边界没有确定。

把 top 到 bottom 之间的每一列分别求和，得到一维数组 column_sum：

column\_sum[j]=\sum_{i=top}^{bottom}a[i][j].

如果再选择第 left 到第 right 列，那么原矩形的元素和就是：

\sum_{j=left}^{right}column\_sum[j].

这正是 column_sum 中从 left 到 right 的连续子段和。因此，固定上下边界后，二维矩形问题就变成了一个一维问题：求最大连续子段和。

一维问题为什么只需要扫描一次

令 dp[j] 表示必须以第 $j$ 列结尾的最大连续子段和。到达第 $j$ 列时只有两种选择：

不接前面的子段，从当前列重新开始，和为 column_sum[j]；
接在第 $j-1$ 列结尾的最优子段后面，和为 dp[j-1] + column_sum[j]。

所以转移为：

dp[j]=\max\bigl(column\_sum[j],\ dp[j-1]+column\_sum[j]\bigr).

代码把它写成 current = max(current, 0) + value：若前面的和 current 为正数，就值得保留；否则丢掉前面，从当前列重新开始。

样例行带压缩与 DP 转移

这张表展示固定第 $2$ 到第 $4$ 行后，每一列如何压成一个数，以及 Kadane 如何决定当前连续子段是重新开始还是接在前面：

列	这一列选中的元素	压缩列和 `value`	重新开始 `value`	接在前面 `previous + value`	`dp`	当前答案
1	`9 + (-4) + (-1)`	4	4	4	4	4
2	`2 + 1 + 8`	11	11	15	15	15
3	`(-6) + (-4) + 0`	-10	-10	5	5	15
4	`2 + 1 + (-2)`	1	1	6	6	15

每一行对应压缩数组的一列；dp 表示必须以当前列结尾的最大连续子段和。比较“重新开始”和“接在前面”两列，就能看出状态转移为何是 dp = max(value, previous + value)。当前答案记录扫描到这一列为止出现过的最大 dp。

怎样枚举所有行带

固定 top 后，先令所有 column_sum[j] = 0。然后让 bottom 从 top 不断向下移动，每加入一行，就执行：

column\_sum[j]\leftarrow column\_sum[j]+a[bottom][j].

这样每个新行带只需 $O(n)$ 更新列和，再用 $O(n)$ 完成一次最大连续子段和扫描。所有上下边界共有 $O(n^2)$ 组，总时间复杂度就是 $O(n^3)$ 。

为什么这样一定正确

任意非空矩形都有唯一的上下边界。算法枚举到这组边界时，column_sum 的任意连续子段和，恰好等于选择相同左右边界的矩形和。最大连续子段和 DP 会在这个行带中找到最优左右边界。

算法枚举了所有上下边界，所以全局答案不会漏掉任何矩形；每次记录的答案又都对应一个真实的非空矩形，因此最终得到的就是最大加权矩形和。

全负矩阵是容易出错的边界。答案必须初始化为负无穷，并且先把当前列加入 current 再更新答案，不能把和为 $0$ 的空子段当成答案。

Python 知识

matrix[top:] 按顺序取得所有可能作为下边界的新行，直接表达“逐行扩大行带”。
[x + y for x, y in zip(column_sum, row)] 把两个等长列表对应位置相加，得到新的列和数组。
current = max(current, 0) + value 是 max(value, current + value) 的等价写法，分别对应“重新开始”和“接在前面”。
状态转移保留普通循环，比用 reduce 压成一行更容易观察全负矩阵和答案更新顺序。

代码

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/**
 * 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-07-16 17:48
 * update_at: 2026-07-19 17:29
 */
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 125;

int n;
int matrix[MAX_N][MAX_N];
int column_sum[MAX_N]; // 当前上下边界之间，每一列的元素和

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> matrix[i][j];
        }
    }

    int answer = INT_MIN;

    for (int top = 1; top <= n; top++) {
        memset(column_sum, 0, sizeof(column_sum));

        for (int bottom = top; bottom <= n; bottom++) {
            int current = 0; // 必须以当前列结尾的最大连续子段和

            for (int column = 1; column <= n; column++) {
                column_sum[column] += matrix[bottom][column];

                // 要么从当前列重新开始，要么接在前一列的最优子段后面。
                current = max(current, 0) + column_sum[column];
                answer = max(answer, current);
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

Python

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19import sys


input = sys.stdin.buffer.readline
n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
answer = float("-inf")

for top in range(n):
    column_sum = [0] * n
    for row in matrix[top:]:
        column_sum = [x + y for x, y in zip(column_sum, row)]

        current = 0
        for value in column_sum:
            current = max(current, 0) + value
            answer = max(answer, current)

print(answer)

复杂度

枚举上下边界需要 $O(n^2)$ ，每个行带更新列和并运行 DP 需要 $O(n)$ ，总时间复杂度为 $O(n^3)$ 。
保存矩阵需要 $O(n^2)$ 空间，列和数组需要 $O(n)$ 额外空间，因此总空间复杂度为 $O(n^2)$ 。
brute.cpp 的时间复杂度为 $O(n^6)$ ，只用于小数据教学与对拍。

总结

这道题最关键的不是直接记住三层循环，而是理解一次降维：固定矩形的上下边界后，把每列压成一个数，左右边界就变成了一维数组中的连续子段。

于是问题分成两个熟悉步骤： $O(n^2)$ 枚举所有行带， $O(n)$ 求每个行带的最大连续子段和，最终得到 $O(n^3)$ 算法。

目录

题意

思路