题解 | 最大子矩阵

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=101;
int matrix[maxn][maxn];
int total[maxn][maxn];
int arr[maxn];
int dp[maxn];
int MaxSubsequence(int n){
    int maxmum=-127;
    for(int i=0;i<n;i++){
        if(i==0){
            dp[i]=arr[i];
        }
        else{
            dp[i]=max(arr[i],dp[i-1]+arr[i]);
        }
        maxmum=max(maxmum,dp[i]);
    }
    return maxmum;
}
int MaxSubmatrix(int n){
    int maxmum=-127;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            for(int k=0;k<n;k++){
                if(i==0){
                    arr[k]=total[j][k];
                }
                else{
                    arr[k]=total[j][k]-total[i-1][k];
                }
            }
            int current=MaxSubsequence(n);
            maxmum=max(current,maxmum);
        }
    }
    return maxmum;
}
int main(){
    int n;
    cin>>n;
    if(n==1){
        int t;
        cin>>t;
        cout<<t<<endl;
    }
    else{
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>matrix[i][j];
            }
        }
        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]=matrix[i][j]+total[i-1][j];
                }
            }
        }
        int answer=MaxSubmatrix(n);
        cout<<answer<<endl;
    }
}