题解 | #最大子矩阵# 枚举

#include <climits>
#include <cstdio>
#include <iostream>
#include <string.h>
using namespace std;
const int N = 105;
int map[N][N];
int pre_j[N][N];  //pre_j[i][j]表示 固定在j这一列中，的前缀和

int main() {
    
    int n;
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            scanf("%d",&map[i][j]);
            pre_j[i][j] = pre_j[i-1][j]+map[i][j];
        }
    }
    int res = INT_MIN;
    //遍历行距
    for(int i1 = 1; i1<=n; i1++){
        for(int i2 = i1;i2<=n; i2++){
            //固定行距，再遍历不同的列，这样就枚举了子矩阵
            int sums[N];
            memset(sums, 0,sizeof(sums));
            for(int j = 1;j<=n;j++){
                //计算当前行距 时，第j列上的和值
                int tmp = pre_j[i2][j] - pre_j[i1-1][j];
                sums[j] = max(sums[j-1]+tmp, tmp);
                res = max(sums[j], res);
            }
        }
    }
    printf("%d", res);
    return 0;
}
// 64 位输出请用 printf("%lld")