最大子矩阵算法详解：从暴力枚举到动态规划

题目描述

给定一个 $n \times n$ 的矩阵，任意选择其连续的 $a$（$0 \le a \le n$）行与 $b$（$0 \le b \le n$）列所确定的一个更小的矩阵就叫作一个子矩阵。一个子矩阵的得分为其每个元素之和，请求出原矩阵的最大子矩阵的得分。

输入格式

从标准输入读入数据。第一行一个正整数 $n$（$1 \le n \le 200$），代表矩阵大小。接下来输入 $n$ 行，每行 $n$ 个整数 $a_{ij}$（$|a_{ij}| \le 100$），代表一个 $n \times n$ 的矩阵。

输出格式

输出到标准输出。输出一个整数，代表最大子矩阵的得分。

样例 #1

样例输入 #1

30 3 -12 -1 4-2 3 -3

样例输出 #1

7

样例2见题目目录下的 2.in 与 2.ans。

C++ 代码实现

算法1：暴力枚举

思路： 从矩阵的第一行开始，枚举子矩阵的行数 $a$ 和列数 $b$，然后枚举子矩阵的起始行和起始列，计算子矩阵的和，取最大值即可。

时间复杂度： 枚举子矩阵的行数和列数需要 $O(n^2)$ 的时间，枚举子矩阵的起始行和起始列需要 $O(n^2)$ 的时间，计算子矩阵的和需要 $O(n^2)$ 的时间，因此总时间复杂度是 $O(n^6)$。

空间复杂度： 不需要额外的空间，空间复杂度是 $O(1)$。cpp#include

using namespace std;

const int MAXN = 205;

int a[MAXN][MAXN];

int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; } } int ans = a[1][1]; for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { for (int i = 1; i + a - 1 <= n; i++) { for (int j = 1; j + b - 1 <= n; j++) { int sum = 0; for (int k = i; k <= i + a - 1; k++) { for (int l = j; l <= j + b - 1; l++) { sum += a[k][l]; } } ans = max(ans, sum); } } } } cout << ans << endl; return 0;}

算法2：暴力枚举优化

思路： 在算法1的基础上，我们可以对计算子矩阵的和进行优化。具体来说，我们可以用一个数组 $s_{i,j}$（$1 \le i,j \le n$）表示从 $(1,1)$ 到 $(i,j)$ 的矩阵的和，即 $s_{i,j}=a_{1,1}+a_{1,2}+\cdots+a_{i,j}$，然后就可以用 $O(1)$ 的时间计算任意子矩阵的和了。

时间复杂度： 枚举子矩阵的行数和列数需要 $O(n^2)$ 的时间，枚举子矩阵的起始行和起始列需要 $O(n^2)$ 的时间，计算子矩阵的和需要 $O(1)$ 的时间，因此总时间复杂度是 $O(n^4)$。

空间复杂度： 需要一个 $n \times n$ 的数组 $s$，空间复杂度是 $O(n^2)$。cpp#include

using namespace std;

const int MAXN = 205;

int a[MAXN][MAXN], s[MAXN][MAXN];

int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; } } int ans = a[1][1]; for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { for (int i = 1; i + a - 1 <= n; i++) { for (int j = 1; j + b - 1 <= n; j++) { int sum = s[i + a - 1][j + b - 1] - s[i - 1][j + b - 1] - s[i + a - 1][j - 1] + s[i - 1][j - 1]; ans = max(ans, sum); } } } } cout << ans << endl; return 0;}

算法3：暴力枚举优化

思路： 在算法2的基础上，我们可以对枚举子矩阵的起始行和起始列进行优化。具体来说，我们可以枚举子矩阵的起始行 $i$，然后枚举子矩阵的起始列 $j$，计算从第 $i$ 行到第 $j$ 行的每一列的和，即 $sum_k=\sum_{l=i}^ja_{l,k}$，然后就可以用 $O(1)$ 的时间计算任意子矩阵的和了。

时间复杂度： 枚举子矩阵的行数和列数需要 $O(n^2)$ 的时间，枚举子矩阵的起始行需要 $O(n)$ 的时间，枚举子矩阵的起始列需要 $O(n)$ 的时间，计算从第 $i$ 行到第 $j$ 行的每一列的和需要 $O(n)$ 的时间，因此总时间复杂度是 $O(n^3)$。

空间复杂度： 需要一个 $n \times n$ 的数组 $s$ 和一个长度为 $n$ 的数组 $sum$，空间复杂度是 $O(n^2+n)=O(n^2)$。cpp#include

using namespace std;

const int MAXN = 205;

int a[MAXN][MAXN], sum[MAXN];

int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; } } int ans = a[1][1]; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { for (int k = 1; k <= n; k++) { sum[k] = (j == i ? 0 : sum[k]) + a[j][k]; } int max_sum = sum[1], min_sum = 0; for (int k = 2; k <= n; k++) { ans = max(ans, sum[k] - min_sum); ans = max(ans, max_sum - min_sum); max_sum = max(max_sum, sum[k]); min_sum = min(min_sum, sum[k]); } } } cout << ans << endl; return 0;}

算法4：动态规划

思路： 定义 $f_{i,j}$ 表示以 $(i,j)$ 为右下角的矩阵的最大和，即 $f_{i,j}=\max_{0\le a\le i,0\le b\le j}\sum_{k=i-a+1}^i\sum_{l=j-b+1}^ja_{k,l}$。显然，$f_{i,j}$ 的值可以通过 $f_{i-1,j}$、$f_{i,j-1}$ 和 $f_{i-1,j-1}$ 推导出来，具体来说，$f_{i,j}$ 可以由 $f_{i-1,j}$、$f_{i,j-1}$ 和 $f_{i-1,j-1}$ 中的最大值加上 $a_{i,j}$ 得到，即 $f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1})+a_{i,j}$。

时间复杂度： 需要计算 $n^2$ 个 $f_{i,j}$，每个 $f_{i,j}$ 需要 $O(n)$ 的时间计算，因此总时间复杂度是 $O(n^3)$。

空间复杂度： 需要一个 $n \times n$ 的数组 $f$，空间复杂度是 $O(n^2)$。cpp#include

using namespace std;

const int MAXN = 205;

int a[MAXN][MAXN], f[MAXN][MAXN];

int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; } } int ans = a[1][1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { f[i][j] = max(f[i - 1][j], max(f[i][j - 1], f[i - 1][j - 1])) + a[i][j]; ans = max(ans, f[i][j]); } } cout << ans << endl; return 0;}

总结

本文介绍了四种解决最大子矩阵问题的算法，分别是暴力枚举、暴力枚举优化、暴力枚举优化和动态规划。其中，暴力枚举的时间复杂度最高，为 $O(n^6)$，而动态规划的时间复杂度最低，为 $O(n^3)$。在实际应用中，我们可以根据矩阵的大小和时间复杂度的要求选择合适的算法。