AcWing 1051. 最大的和
原题链接
简单
作者:
fffzlfk
,
2021-01-31 22:00:15
,
所有人可见
,
阅读 386
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
const int N = 50005;
int n, a[N], f[N], g[N]; // f[i]: 1~i最大连续子段和,g[i]:n~i最大连续子段和
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
fill(f, f+n+2, INT_MIN);
fill(g, g+n+2, INT_MIN);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int s = 0;
for (int i = 1; i <= n; i++) {
s = max(s, 0) + a[i];
f[i] = max(f[i-1], s);
}
s = 0;
for (int i = n; i >= 1; i--) {
s = max(s, 0) + a[i];
g[i] = max(g[i+1], s);
}
int ans = INT_MIN;
for (int i = 1; i < n; i++)
ans = max(ans, f[i] + g[i+1]);
cout << ans << endl;
}
return 0;
}