题解 CF33C 【Wonderful Randomized Sum】
LuckyCloud
2018-06-29 10:12:28
#### 利用数学推导，排除无关变量，然后进行求解。
------------
**应该可以看出，前缀和后缀交叉的情况下，交叉的那部分，相当于没有变化。
那么**
**据题可知：**
**设 前缀为A，后缀为B，未变化部分的为C。序列数字总和为S（允许A，B，C都为空的情况，此时A=B=C=0）**
** 因为 A+B+C=S，需求解为 -（A+B）+C 的最大值**
**所以 —（A+B）+C的最大值 = —（S-C）+C的最大值 = 2C-S **
------------
### 综上 显然S是定值，我们要做的就是让C最大，问题就变成了求最大子段和了。
LuckyCloud
**附上丑陋的代码**
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,Max,S,a[100093],sum,ans;
inline long long read()
{
long long cnt=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){cnt=cnt*10+ch-48;ch=getchar();}
return cnt*f;
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
{
a[i]=read();
sum+=a[i];
}
for (int i=1;i<=n;i++)
if (S+a[i]<0) S=0;
else {S+=a[i];Max=max(Max,S);}
Max=max(Max,S);
ans=Max*2-sum;
printf("%lld\n",ans);
return 0;
}
```