AcWing 1051. 最大的和
原题链接
简单
作者:
ywt51
,
2023-08-05 23:26:06
,
所有人可见
,
阅读 66
算法1:(暴力枚举) $O(n)$
//对区间是否包含a[i]做分类:
// 区间不包含a[i]: f[i] = f[i - 1];
// 区间包含a[i]: f[i] = 以a[i - 1]结尾的最大连续区间和 + a[i];
// 最后枚举所有区间[1, n]中所有可能的分界点, 然后将分界点两边的最大连续和相加取最大值即可;
//f[i]的含义是以i结尾的连续子序列的最大和
//只包含ai或者还包含前面连续的一段,取最大值 f[i] = max(ai, f[i-1]+ai)
#include <bits/stdc++.h>
using namespace std;
const int N = 5E4+10, INF = 1e9;
int T, n, g[N], h[N];
int w[N];
int main(){
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
g[0] = -INF; //存储前缀中的最大值
for (int i = 1, s = -INF; i <= n; ++ i) {
s = max(s, 0) + w[i];
g[i] = max(g[i-1], s);
}
h[n+1] = -INF;
for (int i = n, s = -INF; i; -- i) {
s = max(s, 0) + w[i];
h[i] = max(h[i+1], s);
}
int res = -INF;
for (int i = 1; i <= n; ++ i) //分界点求最大值
res = max(res, g[i] + h[i+1]);
printf("%d\n", res);
}
return 0;
}