题解 | 最大子矩阵

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

// 和大部分不大一样的思路，可以看看。
// 首先同样是枚举这个矩阵的每个点
// 我们有两个dp存储，dph[i][j][h]表示以a[i][j]为矩阵的最右下角，高度为h的最大矩阵值
// dpw[i][j][h]表示以a[i][j]为矩阵的最右下角，宽度为w的最大矩阵值
// 有状态转移方程
// dpw[i][j][w] = max(dpw[i - 1][j][w] + fen, fen)和dph[i][j][h] = max(dph[i][j - 1][h] + fen, fen)
// 以dpw来解释，其中fen表示从a[i][j - w + 1]到a[i][j]的总和
// 因此以a[i][j]为矩阵的最右下角，宽度为w的最大矩阵值就是fen加上以a[i - 1][j]为矩阵的最右下角，宽度为w的最大矩阵值或者fen
// dph的解释同理
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> a(n + 1, vector<int>(n + 1)), b(n + 1, vector<int>(n + 1));
    vector<vector<vector<int>>> dph(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1))),
        dpw(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1)));
    for(int i = 1; i <= n ; i++)
        for(int j = 1; j <= n ; j++) {
            cin >> a[i][j];
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
		  	// b表示二维前缀和
        }

    int ans = -0x3f3f3f3f;
    for(int i = 1; i <= n ; i++)
        for(int j = 1; j <= n ; j++) {
            int res = -0x3f3f3f3f;
            for(int w = 1; w <= j ; w++) {
                int x = i, y = j - w + 1;
                int fen = b[i][j] - b[x - 1][j] - b[i][y - 1] + b[x - 1][y - 1];
                dpw[i][j][w] = max(dpw[i - 1][j][w] + fen, fen);
                res = max(res, dpw[i][j][w]);
            }
            for(int h = 1; h <= i ; h++) {
                int x = i - h + 1, y = j;
                int fen = b[i][j] - b[x - 1][j] - b[i][y - 1] + b[x - 1][y - 1];
                dph[i][j][h] = max(dph[i][j - 1][h] + fen, fen);
                res = max(res, dph[i][j][h]);
            }
            ans = max(ans, res);
        }

    cout << ans;
}

int main() {
    solve();
    return 0;
}

有问题欢迎留言