Maximum Sum on Even Positions

Maximum Sum on Even Positions

 解题思路：

首先，我们知道：如果选择某个子段倒序,那么子段长度一定是偶数，因为如果是奇数长度，那么原来在奇数位置的数还在奇数位置，原来在偶数位置的数还在偶数位置，这对题目要求来说是没有意义的。

那么有两种情况：
第一种： 1,2,3,4,5,6换成6,5,4,3,2,1，跟1,2调换，3,4调换，5,6调换的效果是等效的
第二种： 2,3,4,5,6,7换成7,6,5,4,3,2，跟2,3调换，4,5调换，6,7调换的效果是等效的

对于第一个样例：1 7 3 4 7 6 2 9

如果我们把子段1 7倒序,那么我们多得到的价值是7-1=6

如果我们选1 7 3 4,此时价值在原来基础上加上4-3,此时多得到的总价值是6+1=7

显然，加上整数使我们的总价值增大。如果某个时刻总价值是负数，则像dp求连续子段和一样,舍弃掉

AC_Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;

ll n,a[maxn],ans;
int main()
{
    int t;
    cin>>t;
    while( t-- ){
        cin>>n;
        ll sum1=0,sum2=0,maxx=0;
        ans=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if( i%2==1 ) ans+=a[i];
        }
        for(int i=2;i<=n;i+=2){
            sum1=max((ll)0,a[i]-a[i-1]+sum1);
            maxx = max(maxx,sum1);
        }
        for(int i=3;i<=n;i+=2){
            sum2=max((ll)0,a[i-1]-a[i]+sum2);
            maxx=max(maxx,sum2);
        }
        cout<<ans+maxx<<endl;
    }
    return 0;
}