题解 | 最大子矩阵

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);
typedef long long LL;

const int N=110;
int n;
int a[N][N];
int s[N][N];    //s[i][j]表示第j列前i行的前缀和
int t[N], dp[N];    //t[i]为第i列压缩成一个元素的辅助数组，dp[i]表示t[]前i个元素的最大连续子段和
int ans=-0x3f3f3f3f;

int getmax()
{
    int res=-0x3f3f3f3f;
    dp[1]=t[1];
    for(int i=2; i<=n; i++) dp[i]=max(dp[i-1]+t[i], t[i]);
    for(int i=1; i<=n; i++) res=max(res, dp[i]);
    return res;
}
int main()
{
    IOS
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin>>a[i][j];
    
    for(int j=1; j<=n; j++)
        for(int i=1; i<=n; i++)
            s[i][j]=s[i-1][j]+a[i][j];
    
    for(int i=1; i<=n; i++)//起始行
        for(int j=i; j<=n; j++){//结束行
            for(int k=1; k<=n; k++){
                t[k]=s[j][k]-s[i-1][k];
            }
            ans=max(ans, getmax());
        }
    cout<<ans;
    return 0;
}

N^3的时间复杂度还是很优秀的（N扩展到500依旧很快）

我们把矩阵竖着切成一条一条的，然后前缀和每一列前i个元素之和。

枚举矩阵起始行i和末尾行j，通过前面的前缀和把列上一长条压缩成一个点，这时候辅助数组t就是一维的，数组t的最大连续子段和即为i行到j区域内的最大子矩阵之和

把所有行间最大子矩阵都求出来，取max即为全局最大

#牛客春招刷题训练营#