最大循环子序列和

解题关键：

子序列和最大的两种情况：（1）子序列位于序列中间，不中断

　　　　　　　　　　　　（2）子序列分散在序列两端，此时中间部分的序列和最小，（因为序列总和一定），因此取子序列的最小值t，然后总值-t即为所求；

　　　两种情况取max即可。

#include<bits/stdc++.h>
#define INF 1000000 
using namespace std;
typedef long long ll;
ll a[100002],n;
ll fun(){
    ll sum=0,max1=-INF;
    for(ll i=0;i<n;i++){
        sum+=a[i];
        if(sum>max1) max1=sum;
        if(sum<0) sum=0;
    }
    return max1;
}
int main(){
    scanf("%lld",&n);
    ll sum=0;
    for(ll i=0;i<n;i++){
        scanf("%lld",a+i);
        sum+=a[i];
    }
    ll t1=fun();
    for(ll i=0;i<n;i++){
        a[i]=-a[i];
    }
    ll t2=fun();
    ll ans=max(t1,sum+t2);
    printf("%lld
",ans);
}