最大子矩阵：二维前缀和算法详解及 C++ 代码实现

最大子矩阵：二维前缀和算法详解及 C++ 代码实现

问题描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3
0 3 -1
2 -1 4
-2 3 -3

样例输出 #1

7

算法分析

这是一道比较经典的二维前缀和题目，我们可以先预处理出二维前缀和数组 s_{i,j} 表示以 (i,j) 为右下角的矩阵元素之和，然后枚举子矩阵的上下边界 i_1,i_2，以及左右边界 j_1,j_2，然后用二维前缀和快速计算出子矩阵的元素之和，取其中的最大值即可。

时间复杂度

预处理二维前缀和数组的时间复杂度为 O(n^2)，枚举子矩阵的时间复杂度为 O(n^4)，计算子矩阵元素之和的时间复杂度为 O(1)，因此总时间复杂度为 O(n^4)，可以通过此题。

C++ 代码

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

const int MAXN = 205;
int n, a[MAXN][MAXN], s[MAXN][MAXN];

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

    // 预处理二维前缀和数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }

    // 枚举子矩阵的上下边界和左右边界
    int ans = -1e9;
    for (int i1 = 1; i1 <= n; i1++) {
        for (int i2 = i1; i2 <= n; i2++) {
            for (int j1 = 1; j1 <= n; j1++) {
                for (int j2 = j1; j2 <= n; j2++) {
                    // 使用二维前缀和计算子矩阵的元素之和
                    int sum = s[i2][j2] - s[i2][j1 - 1] - s[i1 - 1][j2] + s[i1 - 1][j1 - 1];
                    ans = max(ans, sum);
                }
            }
        }
    }

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