Educational Codeforces Round 90 (Rated for Div. 2)D

D - Maximum Sum on Even Positions

题解：
首先我们可以得知，反转偶数段的效果就是让这一段的奇偶反转，这样的话，问题就得到了简化。
我们用一个数组储存相邻之间的积偶差值（奇数-偶数）
有两种情况（数字为下标）
第一种： 1-2 3-4 5-6 这些数字之间调换
第二种： 2-3 4-5 6-7 这些数字之间进行调换
所以我们拿出b，c两个数组来储存着两种差值情况。
然后我们找到最大连续区间和（b，c）这两个数组。
说明一下这个最大值，为什么直接加上这个最大值，因为这个值代表的是反转某段区间后，总值可以加多少
找一个最大值，加上偶区间的数字大小即可。
时间复杂度O(n)

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 2e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
ll a[maxn];
ll b[maxn];
ll c[maxn];
ll maxsum(ll a[],int n)
{
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        if(a[i-1]>0)a[i]+=a[i-1];
        else a[i]+=0;
        if(a[i]>ans) ans=a[i];
    }
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        ll ans=0;
        int n;
        scanf("%d",&n);
        for(int i=0;i<n+5;i++){
            a[i]=b[i]=c[i]=0;
        }
        for(int i=0;i<n;i++){
            scanf("%lld",&a[i]);
            if(i%2==0)ans+=a[i];
        }
        int cnt=0;
        for(int i=0;i<n;i+=2){
            b[cnt++]=a[i+1]-a[i];
        }
        cnt=0;
        for(int i=2;i<n;i+=2){
            c[cnt++]=a[i-1]-a[i];
            //cout<<c[i]<<endl;
        }
//        for(int i=0;i<n;i++) cout<<b[i]<<" ";
//        cout<<endl;
//        for(int i=0;i<n;i++) cout<<c[i]<<" ";
//        cout<<endl;
        ll imax=maxsum(b,n/2+2);
        imax=max(imax,maxsum(c,n/2+2));
        //cout<<ans<<" "<<imax<<endl;
        printf("%lld\n",ans+imax);
    }
    return 0;
}