44 lines
1.2 KiB
C++
44 lines
1.2 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
typedef long long LL;
|
||
const int N = 4e5 + 10;
|
||
|
||
int n;
|
||
LL a[N], s[N]; // 原数组，前缀和数组
|
||
int q[N], L, R; // 滑动窗口，左端点，右端点
|
||
LL ans; // 答案
|
||
int main() {
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++) {
|
||
cin >> a[i];
|
||
a[n + i] = a[i]; // 破环成链
|
||
}
|
||
|
||
for (int i = 1; i <= 2 * n; i++) // 一维前缀和
|
||
s[i] = s[i - 1] + a[i];
|
||
|
||
// 滑动窗口
|
||
L = R = 1; // 初始化滑动窗口长度为0
|
||
ans = -1e18; // 初始化答案为-1e18
|
||
|
||
for (int i = 1; i <= 2 * n; i++) {
|
||
// 维护滑动窗口，确保窗口长度不超过n
|
||
while (L <= R && q[L] < i - n)
|
||
L++;
|
||
|
||
// 计算当前位置i与窗口内最小前缀和的差，即为以i结尾的最大子段和
|
||
LL currentSum = s[i] - s[q[L]];
|
||
ans = max(ans, currentSum);
|
||
|
||
// 维护单调队列，保证队列中的前缀和是单调递增的
|
||
// 如果新的前缀和更小，则队尾的更大值都不可能是最优解，可以删除
|
||
while (L <= R && s[i] < s[q[R]])
|
||
R--;
|
||
|
||
// 将当前位置加入队列
|
||
q[++R] = i;
|
||
}
|
||
|
||
printf("%lld\n", ans); // 输出答案
|
||
return 0;
|
||
} |