这题难度评得是不是太低了 qwq，它在 CF 上的过题人数甚至不到两千。
分析
我们记读入的数组为 w[]。
我的思路是从左到右枚举位置 (i)，然后找 (i) 最左边的点 (x) 使得对于 (jin [x, i-1]) 有 (w[i] leq w[i])，类似地找到 (i) 最右边的点 (y) 使得 (jin [i+1, y]) 有 (w[y]leq w[i])。
因为最值是具有单调性的，我们可以用二分和 ST 表来实现上面的查找过程。
接下来我们从 ([x, i-1]) 找到最大的后缀和以及从 ([i+1, y]) 找到最大的前缀和，这一步也可以用 ST 表来解决，最后更新答案即可。
细节见代码：
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=1e5+5;
int n;
int w[N];
int Log[N];
void init(){
Log[1]=0;
rep(i,2,N-1) Log[i]=Log[i/2]+1;
}
struct ST{
int f[N][25];
void init(int *a){
rep(i,1,n) f[i][0]=a[i];
}
void build(){
rep(j,1,20) for(int i=1; i+(1<<j)-1<=n; i++)
f[i][j]=max(f[i][j-1], f[i+(1<<j-1)][j-1]);
}
int query(int l, int r){
int k=Log[r-l+1];
return max(f[l][k], f[r-(1<<k)+1][k]);
}
}a, p, q;
int pre[N], suf[N];
int find(int l, int r, int v, bool op){
int L=l, R=r;
if(op){
while(L<R){
int mid=L+R>>1;
if(a.query(mid, r)<=v) R=mid;
else L=mid+1;
}
if(a.query(L, r)>v) return 0;
else return L;
}
else{
while(L<R){
int mid=L+R+1>>1;
if(a.query(l, mid)<=v) L=mid;
else R=mid-1;
}
if(a.query(l, L)>v) return 0;
else return L;
}
}
int main(){
init();
read(n);
rep(i,1,n) read(w[i]), pre[i]=pre[i-1]+w[i];
dwn(i,n,1) suf[i]=suf[i+1]+w[i];
a.init(w);
p.init(pre);
q.init(suf);
a.build(), p.build(), q.build();
int res=0;
rep(i,1,n){
int x, y;
x=y=0;
if(i-1>0) x=find(1, i-1, w[i], 1);
if(i+1<=n) y=find(i+1, n, w[i], 0);
int t=0;
if(x) t+=max(0, q.query(x, i-1)-suf[i]); // 这里需要取 max(0, )，因为我们有权利不取这部分。
if(y) t+=max(0, p.query(i+1, y)-pre[i]);
res=max(res, t);
}
cout<<res<<endl;
return 0;
}
附送 debug 数据：
in:
202
28 17 17 -25 -26 -17 18 1 16 -26 -30 8 -22 17 -20 16 -23 16 -25 3 21 27 -21 -16 -8 21 -22 19 10 -11 -18 -27 -15 -4 6 -22 -30 -25 -18 -6 -27 18 -17 -7 -30 -16 -30 -17 -23 21 -16 27 -14 -18 18 -7 -4 -28 -19 -23 27 0 -8 -6 4 -3 -3 28 -30 11 -10 -2 6 -21 1 -13 -22 -22 22 -9 -23 -6 19 4 -10 -10 -12 10 -25 -3 -20 -29 28 10 7 11 17 27 -30 -20 -12 -24 16 -23 -10 -7 -29 -12 -25 -30 -18 24 11 -23 4 8 0 -11 -3 21 -2 3 -25 -18 2 -26 4 5 27 15 -11 -23 4 -8 -14 -6 13 -20 -3 1 24 4 -4 -19 -29 -11 -25 -7 -7 26 -11 23 -19 -2 -15 0 5 -3 -23 24 2 19 -14 28 -9 -26 -9 -5 -23 -7 -22 6 -6 -23 -9 8 17 -29 -12 -4 4 14 8 -24 -1 -5 -28 -23 24 17 -25 12 -29 14 13 17 -11 19 27 6 -17 3
out:
72
=======================
in:
7
-5 7 -10 1 1 -8 3
out:
1