AcWing 126. 最大的和
原题链接
简单
作者:
我要出去乱说
,
2021-02-11 15:37:16
,
所有人可见
,
阅读 317
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int s[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) //在列方向上预处理出前缀和
for (int j = 1; j <= n; j ++ ) //所有前缀和题目下标都从1开始,这样不用处理边界问题
{
int x;
cin >> x;
s[i][j] = s[i - 1][j] + x;
}
int res = -128;
for (int i = 1; i <= n; i ++ ) //枚举行列,i是上界j是下界
for (int j = i; j <= n; j ++ )
{
int last = 0; //last表示以k结尾的子序列的最大值
for (int k = 1; k <= n; k ++ )
{
int w = s[j][k] - s[i - 1][k]; //计算第k列,从i行到j行元素和
last = max(last, 0) + w; //当last < 0,舍去
res = max(res, last);
}
}
cout << res << endl;
return 0;
}