AcWing 126. 最大的和
原题链接
简单
作者:
Dybala
,
2021-02-13 23:50:43
,
所有人可见
,
阅读 471
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int a[200][200];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){//列方向上取出前缀和
for(int j=1;j<=n;j++){
int key;
cin>>key;
a[i][j]=a[i-1][j]+key;
}//其中a表示某列元素的和
}
int res=-10000;
for(int i=1;i<=n;i++){//枚举上下界
for(int j=i;j<=n;j++){
int f=0;
for(int k=1;k<=n;k++){
int w=a[j][k]-a[i-1][k];
f=max(f,0)+w;
res=max(res,f);
}
}
}
cout<<res<<endl;
return 0;
}