题解 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;
}
```