AcWing 126. 最大的和
原题链接
简单
作者:
Egqawkq
,
2021-02-05 14:27:53
,
所有人可见
,
阅读 288
直接附上代码,比较好理解
#include<iostream>
#include<climits>
using namespace std;
const int N = 1e2 + 10;
int n;
int g[N][N];
int s[N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for(int i = 1;i <=n ;i++){
for(int j = 1;j<=n;j++){
int x;
cin >> x;
// s[i][j] 代表了从第1行到第i行为止第j列的前缀和
s[i][j] = s[i-1][j] + x;
}
}
int ret = -0x3f3f3f3f;
for(int i = 1;i <= n;i++){
for(int j = i ;j <=n;j++){
int last = 0; //表示以k结尾的子序列的最大值
//枚举一下i行到j行哪一个子矩阵最大
for(int k = 1;k <= n;k++){
last = max(last,0) + s[j][k] - s[i-1][k];
ret = max(ret,last);
}
}
}
cout << ret << endl;
return 0;
}