AcWing 126. 最大的和
原题链接
简单
作者:
wyf
,
2021-01-29 22:11:34
,
所有人可见
,
阅读 466
二维前缀和暴力做:通过观察数据范围发现可以使用二维前缀和暴力枚举,每一个矩阵的和,最后求出最大值
#include<iostream>
using namespace std;
const int N=110;
int g[N][N],s[N][N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>g[i][j];
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+g[i][j];
}
int res=-1e9;
for(int x1=1;x1<n;x1++)
for(int y1=1;y1<n;y1++)
for(int x2=x1;x2<=n;x2++)
for(int y2=y1;y2<=n;y2++)
res=max(res,s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
cout<<res<<endl;
return 0;
}