最大子矩阵和 $ n^3 $ 算法
$ solution: $
首先我们不难想到枚举上下左右边界，然后两层循环统计权值和，复杂度 $ O(n^6) $ 。这个我们用前缀和可以省去后面的循环，将复杂度降成 $ O(n^4) $ 。然后我们考虑不枚举上下左右四个边界，我们只枚举其中的上边界和下边界，于是题目转化成一个一维找权值最大区间。
于是我们考虑一个问题：怎样求一个数列的最大子段和。这个用DP可以做，设 $ f[i] $ 表示以 $ i $ 为右端点的最大字段和， $ f[i]=max(f[i-1]+a[i],a[i]) $ 这个我们可以 $ O(n) $ 计算。
于是我们求出这整个矩阵的向上的前缀和 $ s[i][j]=a[i][j]+s[i-1][j] $ ，这个可以 $ O(1) $ 求出上述一维状态下的权值。
总复杂度 $ O(n^3) $
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n,ans;
int s[105][105];
int a[105],f[105];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=qr(); f[0]=-1e9; ans=-1e9;
for(rg i=1;i<=n;++i)
for(rg j=1;j<=n;++j)
s[i][j]=s[i-1][j]+qr();
for(rg i=0;i<n;++i)
for(rg j=i+1;j<=n;++j)
for(rg k=1;k<=n;++k){
a[k]=s[j][k]-s[i][k];
f[k]=max(f[k-1]+a[k],a[k]);
ans=max(ans,f[k]);
}
printf("%d\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/812-xiao-wen/p/11252431.html
