AcWing 126. 最大的和(二维前缀和 + 枚举)
原题链接
简单
作者:
Value
,
2021-03-04 18:46:34
,
所有人可见
,
阅读 273
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N], sum[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];
}
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= n; j ++ ){
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
}
int maxv = -0x3f3f3f;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
for(int k = i; k <= n; k ++ )
for(int m = j; m <= n; m ++ )
maxv = max(maxv, sum[k][m] - sum[i - 1][m] - sum[k][j - 1] + sum[i - 1][j - 1]);
cout << maxv << endl;
return 0;
}