题面
给定一个长度为 \(n\) 数列 \(a\)，保证每项都不为 \(0\)。初始时 \(x=0\)，然后对于 \(1\le i\le n\)，按顺序进行如下操作：
- 如果 \(x\ge k\)，则 \(x\rightarrow \max(k, x+a_i)\)，否则 \(x\rightarrow x+a_i\)。
你需要求出 \(k\)，使得 \(x\) 的值尽量大。
题解
如果我们不考虑 \(k\) 的影响，将 \(x\) 的变化曲线画出来，可以发现为一段折线。下面考虑 \(k\) 的影响：可以使一段趋势为向下的折线变化量为 \(0\)，那么 \(k\) 对总答案的贡献即为改变的这一段折线的变化量。考虑最大化该变化量，即在原数列中寻找最小区间和。
考虑处理出原数列的前缀和 \(sum\)，计算时枚举右端点 \(r\)，以 \(r\) 为右端点的区间最小区间和为 \(sum_r - \max\limits_{1 \le l < r} sum_l\)，开一个变量维护即可。总复杂度 \(\mathcal{O}(n)\)。
Code
//CodeForces - 1845D
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::pair<valueType, valueType> ValuePair;
int main() {
valueType T;
std::cin >> T;
for (int testcase = 0; testcase < T; ++testcase) {
valueType N;
std::cin >> N;
ValueVector source(N);
for (auto &iter: source)
std::cin >> iter;
std::partial_sum(source.begin(), source.end(), source.begin());
ValuePair ans(0, 0);
valueType maxSum = 0;
for (auto const &iter: source) {
ans = std::min(ans, std::make_pair(iter - maxSum, maxSum));
maxSum = std::max(maxSum, iter);
}
std::cout << ans.second << '\n';
}
}