Codeforces 33C Wonderful Randomized Sum

Codeforces 33C Wonderful Randomized Sum

题目链接

题目大意：

一个数字序列  可以选择它的一些前缀或后缀中的每个数字都乘以 -1

前缀和后缀可以交叉也可以为空 

问能得到的最大序列和是多少

解题思路：

前缀和为 A  后缀和为B 那么中间的就是 C

总和为 S  

S=A+ B + C

所求等于  -（A+B）+C

    ==   -（S-C）+C

    ==  2*C - S

所以求中间的最大和就行了

代码如下：
 

#include<iostream>
using namespace std;
int main()
{int n,i,x;int ans=0;int sum=0;int maxx=0;cin>>n;for(i=0;i<n;i++){cin>>x;sum+=x;ans+=x;maxx=max(ans,maxx);if(ans<=0)ans=0;}cout<<2*maxx-sum<<endl;return 0;
}