AcWing 126. 最大的和(枚举+前缀和)
原题链接
简单
作者:
xybh
,
2021-02-03 16:52:15
,
所有人可见
,
阅读 338
枚举+前缀和
#include<iostream>
using namespace std;
const int N = 105;
int s[N][N], a[N][N];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> a[i][j];
// 求当前列的前缀和
s[i][j] = s[i-1][j] + a[i][j];
}
}
int res = -300;
// 枚举下界
for(int i = 1; i <= n; i++){
// 枚举上界
for(int j = i; j <= n; j++){
int f = 0;
// 枚举每一列
for(int l = 1; l <= n; l++){
// 当前上下界的值
int w = s[j][l] - s[i-1][l];
// 前一列的值
f = max(f, 0) + w;
// 判断当前值是否最大
res = max(res, f);
}
}
}
cout << res;
return 0;
}