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

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

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

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

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