CF33C Wonderful Randomized Sum
我们可以发现，如果两区间不交叉也不会影响到结果，所以我们只需要考虑不交叉的情况即可。
我们所选择的前缀\(1\sim i\)应满足区间和最小，后缀也一样。所以用两个数组\(lr,rl\)分别记录下\(1\sim i\)（前缀）最小和、\(i\sim n\)（后缀）最小和。然后枚举分割点\(i\)，把前缀和后缀的和取一个最小值。答案即为\(sum-2*min(lr[i],rl[i+1])\quad(1\leq i \leq n)\)（\(sum\)是所有元素的和）。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100010],lr[100010],rl[100010],sum;
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
for(int i=1,cur=0;i<=n;i++) cur+=a[i],lr[i]=min(lr[i-1],cur);
for(int i=n,cur=0;i>=1;i--) cur+=a[i],rl[i]=min(rl[i+1],cur);
int minn=LLONG_MAX;
for(int i=1;i<=n;i++) minn=min(minn,lr[i]+rl[i+1]);
cout<<sum-2*minn;
return 0;
}