很容易的想到，用二維前綴和，暴力的4層for枚舉左上角和右下角的下標。
這樣肯定會超時。

我們不妨先考慮一維的情況，一個數(shù)組，如何求最大的矩形。
這是一個很簡單的DP
f[i]=max(f[i-1],0)+a[i] f[i] 表示以i結(jié)尾的最大值 最后以所有結(jié)尾的取一個max就是結(jié)果

這時候我們就可以借助列的前綴和，我們通過枚舉上下邊界，
將一個個等高列的矩陣當成一個屬數(shù)，這樣就可以按照剛才一維的方法求解。
此時是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; }

總結(jié)

以上是生活随笔為你收集整理的126. 最大的和【思维 前缀和】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。