题目大意
玩家的初始积分为0，该玩家连续进行\(n\)场比赛，每场比赛可升高或降低玩家的积分(\(a_i\))。你可以设置一个\(k\)值，比赛过程中玩家的积分不会低于\(k\)(若有一场比赛会使玩家的积分低于\(k\)，比赛后玩家的积分会被强制变为\(k\))。找到一个\(k\)，使经过\(n\)场比赛后玩家的总积分最大。
解题思路
设置\(k\)的操作会使玩家少减少一定数量的积分，我们只用找到序列的连续最小子串和，并设置\(k\)使得这部分的减少量为0，即可满足题意。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
ll a[N];
void work()
{
//寻找最小子串和
int n; cin >> n;
ll mx = 0, sum = 0, x;
ll delta = 0, ans = 0;
for (int i = 0; i < n; ++i)
{
cin >> x; sum += x;
mx = max(mx, sum);
//当前前缀和减去最大子前缀和，即可得到以当前元素为结尾的最小子串和
if (sum - mx < delta)
{
delta = sum - mx;
ans = mx;
}
}
cout << ans << endl;
}
int main()
{
int T; cin >> T;
while (T--)
{
work();
}
return 0;
}