题解 | #最大子矩阵#

#include <iostream>
using namespace std;

const int N=110;
int a[N][N];
int s[N][N];
int main() {
    int n,max=-128;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            if(a[i][j]>max) max=a[i][j];
        }
    }     
    //初始化前缀和数组
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    //枚举起始坐标
    for(int sx=1;sx<=n;sx++){
        for(int sy=1;sy<=n;sy++){
            //枚举终点坐标
            for(int i=sx;i<=n;i++){
                for(int j=sy;j<=n;j++){
                    int res=s[i][j]-s[sx-1][j]-s[i][sy-1]+s[sx-1][sy-1];
                    if(res>max) max=res;
                }
            }
        }
    }
    cout<<max<<endl;
    return 0;
}