#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即为全局最大