3041: 最大子矩阵 应该能看懂吧

解题思路:

注意事项:
参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义全局变量n和三个二维数组a, b, c，以及答案变量ans
int n, a[110][110], b[110][110], c[110][110];
int ans = -1000;
int main() {
    // 读取矩阵的大小n
    cin >> n;
    // 读取矩阵a的元素
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    // 计算前缀和矩阵b，b[i][j]表示从(1,1)到(i,j)的子矩阵元素之和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            b[i][j] = b[i-1][j] + a[i][j];
        }
    }
    // 计算前缀和矩阵c，c[i][j]表示从(1,1)到(i,j)的子矩阵元素之和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            c[i][j] = c[i][j-1] + b[i][j];
        }
    }
    // 枚举所有可能的子矩阵，并计算其元素之和，更新最大值ans
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k < i; k++) {
                for (int l = 0; l < j; l++) {
                    // 计算当前子矩阵的元素之和
                    int kkk = c[i][j];
                    kkk = kkk - c[i][l] - c[k][j] + c[k][l];
                    // 更新最大值
                    ans = max(ans, kkk);
                }
            }
        }
    }
    // 输出最大子矩阵的元素之和
    cout << ans << endl;
    return 0;
}