codeforces 33C最大子序列

codeforces 33C最大子序列

如果前缀后缀交叉，交叉部分值不变，那么求出原序列的最大子序列，最大子序列前后部分一定是负的，翻转前后部分得到最大的序列，ans=最大子序列-(总和-最大子序列）。

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
int a[100010]; 
int n,sum,maxn,ans;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}for(int i=1;i<=n;i++){maxn=max(maxn+a[i],0);ans=max(maxn,ans);}cout<<ans-(sum-ans)<<endl;
}