126. 最大的和【思维 前缀和】

很容易的想到，用二维前缀和，暴力的4层for枚举左上角和右下角的下标。
这样肯定会超时。

我们不妨先考虑一维的情况，一个数组，如何求最大的矩形。
这是一个很简单的DP
f[i]=max(f[i-1],0)+a[i] f[i] 表示以i结尾的最大值 最后以所有结尾的取一个max就是结果

这时候我们就可以借助列的前缀和，我们通过枚举上下边界，
将一个个等高列的矩阵当成一个属数，这样就可以按照刚才一维的方法求解。
此时是3层的for,降了一维 。

#include<bits/stdc++.h> using namespace std; const int N=110; int a[N][N],s[N][N],n; int main(void) {cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) s[j][i]=s[j-1][i]+a[j][i];//列的前缀和int ans=-1e9;for(int l=1;l<=n;l++)//上界{for(int r=l;r<=n;r++)//下界{int temp=0;for(int i=1;i<=n;i++){temp=max(temp,0)+(s[r][i]-s[l-1][i]);ans=max(ans,temp);}}}cout<<ans;return 0; }

总结

以上是生活随笔为你收集整理的126. 最大的和【思维 前缀和】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。