题解 | #最大子矩阵#

矩阵：连续行×连续列

每次选定若干连续行之后，将其整体视为一行，就可类比最大子序列和，用DP求解

#include <climits>
#include <iostream>
using namespace std;
const int maxn=101;
const int INF=INT_MIN;

int s[maxn][maxn];//输入
int sum[maxn][maxn];//辅助数组：前i行累加到一行,便于后续计算
int ans[maxn];//转化为一维数组：若干连续行视为一行
int dp[maxn];

int maxmatrix(int n){//求解一维最大子序列和
    int result=INF;
    for(int i=0;i<n;i++){
        if(i==0)dp[i]=ans[i];
        else dp[i]=max(ans[i],dp[i-1]+ans[i]);
        result=max(result,dp[i]);
    }
    return result;
}

int main() {
    int n;
    while (scanf("%d",&n)!=EOF) {

        for(int i=0;i<n;i++){//输入
            for(int j=0;j<n;j++){
                scanf("%d",&s[i][j]);
            }
        } 

        for(int i=0;i<n;i++){//计算辅助数组
            for(int j=0;j<n;j++){
                if(i==0)sum[i][j]=s[i][j];
                else sum[i][j]=sum[i-1][j]+s[i][j];
            }
        }

    int result=INF;

    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){//i~j行视为一行
            for(int col=0;col<n;col++){
                 if(i==0)ans[col]=sum[j][col];
                 else ans[col]=sum[j][col]-sum[i-1][col];
            }
            result=max(result,maxmatrix(n));
        }
    }
    printf("%d\n",result);
    
    }

    return 0;
}