题解 | #最大子矩阵#

#include <iostream>
using namespace std;
const int maxn=100;
int ary[maxn];
int matrix[maxn][maxn];
int total[maxn][maxn];
int dp[maxn];
int maxsub(int n){
    dp[0]=ary[0];
    int m=dp[0];
    for(int i=1;i<n;i++){
        dp[i]=max(dp[i-1]+ary[i],ary[i]);
        m=max(m,dp[i]);
    }
    return m;

}
void Minput(int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>matrix[i][j];
        }
    }
}
void Gtotal(int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==0) total[i][j]=matrix[i][j];
            else{
                total[i][j]=total[i-1][j]+matrix[i][j];
            }
        }
    }
}
int findMaxSubMatrix(int n){
    int MAX=-100;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            for(int k=0;k<n;k++){
                if(i==0) ary[k]=total[j][k];
                else ary[k]=total[j][k]-total[i-1][k];
            }
            MAX=max(MAX,maxsub(n));
        }
    }
    return MAX;
}
int main() {
    int n;
    while(cin>>n){
        Minput(n);
        Gtotal(n);
        cout<<findMaxSubMatrix(n)<<endl;

    }
}