牛客网：最大子矩阵

 

1.前缀和

用一个暴力的前缀和来做，这个子矩阵，我们可以用左上角的坐标和右下角的坐标共同确定，我们在读入数据的时候，用一个数组来存储以(1,1)为左上角，(i,j)为右下角的矩阵和。

sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j]

之后我们再固定左上角(x,y)，遍历所有的右下角(i,j)（包括左上角本身），然后这两者组成的矩阵和可以这样求:

sum = sum[i][j]-sum[x-1][j]-sum[i][y-1]+sum[x-1][y-1]

#include<bits/stdc++.h>
using namespace std;
const int N=101;
int sum[N][N];
int n;

void get(int x, int y, int &res){
    for(int i=x;i<=n;++i){
        for(int j=y;j<=n;++j){
            int t=sum[i][j]-sum[x-1][j]-sum[i][y-1]+sum[x-1][y-1];
            if(t>res){
                res=t;
            }
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            int t;
            cin>>t;
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+t;
        }
    }
    int res=0x80000001;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            get(i,j,res);
        }
    }
    cout<<res<<endl;
}

2.动态规划&&前缀和

dp的思路是先在读入数据的时候求出每一列的前缀和。

之后固定两行，遍历列。在遍历列的过程中有点像在求一个一维数组的最大连续和。在遍历过程中选出最大值。

这里的时间复杂度是O(n^3)，比起上边那个O(n^4)，利用前缀和将求矩阵的和的复杂度降低。

#include <bits/stdc++.h>
using namespace std;
const int N=510,inf=1e18;
typedef long long ll;
ll a[N][N],sum[N][N],dp[N];
int main()
{
    ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            sum[i][j]=sum[i-1][j]+a[i][j]; // 第j列前i行的前缀和
        }
    }
    ll mx=-inf;
    for(int k1=1;k1<=n;k1++) // 行 上端点
    {
        for(int k2=k1;k2<=n;k2++) // 行 下端点
        {
            //dp[0]=0;
            for(int i=1;i<=n;i++) // 列
            {
                ll tmp=sum[k2][i]-sum[k1-1][i]; // 第i列 [k1,k2]行之和
                dp[i]=max(dp[i-1]+tmp,tmp); // 最大子段和求法
                mx=max(mx,dp[i]);
            }
        }
    }
    printf("%lld\n",mx);
    return 0;
}