题解 | 最大子矩阵

#include <iostream>
#include <algorithm>

using namespace std;
#define N 101
int a[N][N];    // 用来存储原数组
int tmp[N]; // 用来存储压缩后的数组
int n;

int getMaxSubArrSum(){
    int res = -1e8;
    int cur_max = -1000;
    for(int i = 1; i <= n; ++i){
        cur_max = max(tmp[i],tmp[i]+cur_max);
        res = max(res,cur_max);
    }
    return res;
}

int GetMaxSubMetricSum(){
    int res = -1e8;
    for(int btm = 1; btm <= n; ++btm){  // btm : bottom
        for(int i = 1; i <= n; ++i) tmp[i] = 0; // 先清空上一轮的数据
        for(int top = btm; top <= n; ++top){
            // 先将本层数据加上来
            for(int i = 1; i <= n; ++i)
                tmp[i] += a[top][i];
            int cur_max = getMaxSubArrSum();
            res = max(res, cur_max);
        }
    }
    return res;
}

int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            scanf("%d",&a[i][j]);
    cout << GetMaxSubMetricSum() << endl;

    return 0;
}