CF33C Wonderful Randomized Sum

CF33C Wonderful Randomized Sum

题意：给你一个数组 你可以其任意长度前缀 和任意长度后缀乘以 -1 最后求 这样操作能得到的 数组 每项之和最大

问题分析：

设 前缀和为 s1 中间部分和为 s2 后面部分和 为s3 整个数组的和为 s 呢么 s=s1+s2+s3即 s1+s3=s-s2 所求操作之后的 数组和 为 S= - (s1+s3)+s2 = - (s-s2)+s2 = s2*2 -s

由于s为定值，要求的最大值 只要保证s2最大就行了 转变成了 求最大区间和 具体看代码

AC代码：

#include<iostream> #include<cstdio> #include<cstring> #include<bitset> #include<sstream> #include<string.h> #include<iomanip> #include<cmath> #include<algorithm> #include<cstdlib> #include<set> #include<map> #include<queue> #include<vector> using namespace std; #define ll long long #define lowbit(x) (x)&(-x) #define mem(a,b) memset((a),(b),sizeof(a)); const ll inf=0x3f3f3f3f;//1061109567,2*未超int，allinf=mem(a,0x3f,sizeof(a)); typedef pair<int ,int > PII; const int nn=1e6+10; int a[nn],b[nn],re[nn],de[nn]; int main() { //#define io #ifdef io freopen("in.txt","r",stdin); #endif int n; cin>>n; int sum=0,ans=0,ma=0; for(int i=0;i<n;i++){ int x; cin>>x; sum+=x;//统计定值 s if(ans+x>0)ans+=x;//从正项开始 大于0就++ else ans=0;//小于0就 开辟新的区间（相当于新的段首） ma=max(ans+x,ma);//每次 取最大值 防止丢失 } cout<<ma*2-sum<<endl; return 0; }