题解 | 最大子矩阵

#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
const int MAXN =100;
int martix[MAXN][MAXN];
int total[MAXN][MAXN];//辅助矩阵记录每列和
int arr[MAXN];//等价一维数组
int dp[MAXN];//计算大小数组
int MaxSubsequence(int n){
    int maximum=INT_MIN;//防止负数情形
    for(int i=0;i<n;i++){
        if(i==0){
            dp[i] =arr[i];
        }else{
            dp[i]=max(arr[i],arr[i]+dp[i-1]);
        }
        maximum=max(maximum,dp[i]);
    }
    return maximum;
}
int MaxSubmartix(int n){
    int maximum=INT_MIN;
    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);
            maximum = max(maximum,current);
        }
    }
    return maximum;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int temp=0;
            scanf("%d",&martix[i][j]);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==0){
                total[i][j]=martix[i][j];
            }else{
                total[i][j] =total[i-1][j]+martix[i][j];
            }
        }
    }
    cout<<MaxSubmartix(n)<<endl;
    return 0;
}