传送门
题意：给一个数组，问最多选一个子数组reverse一次之后最大的偶数位元素之和为多少。
题解：选一个长度为奇数的子数组reverse不改变答案。所以考虑reverse一个长度为偶数的子数组。大致乱搞思想：默认取偶数位时，选某一段区间连续取奇数位，最大和位多少，以及默认取奇数位时，选某一段连续取偶数位的最大和。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+4;
int n;
int a[N],t[N];
ll ans;
ll f[2][2][N>>1];//cur, used, pos
inline void smax(ll &x,ll y) {x=x<y?y:x;
}
inline int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();return x*f;
}
inline void clear(int tot) {for (register int i=1;i<=tot;++i) {f[0][0][i]=0;f[1][1][i]=0;f[0][1][i]=0;}
}
inline ll calc_od(int l,int r) {//default position is oddint tot=0;for (register int i=l;i<=r;++i) t[++tot]=a[i];ll ret=0;for (register int i=1;i<=tot;++i) {smax(f[0][0][i],f[0][0][i-1]+t[(i<<1)-1]);smax(f[1][1][i],max(f[1][1][i-1],f[0][0][i-1])+t[i<<1]);smax(f[0][1][i],max(f[0][1][i-1],f[1][1][i-1])+t[(i<<1)-1]);}smax(ret,f[0][0][r>>1]);smax(ret,f[1][1][r>>1]);smax(ret,f[0][1][r>>1]);clear(tot);return ret;
}
inline ll calc_ev(int l,int r) {//default position is evenint tot=0;for (register int i=l;i<=r;++i) t[++tot]=a[i];ll ret=0;for (register int i=1;i<=tot;++i) {smax(f[0][0][i],f[0][0][i-1]+t[i<<1]);smax(f[1][1][i],max(f[1][1][i-1],f[0][0][i-1])+t[(i<<1)-1]);smax(f[0][1][i],max(f[0][1][i-1],f[1][1][i-1])+t[i<<1]);}smax(ret,f[0][0][r>>1]);smax(ret,f[1][1][r>>1]);smax(ret,f[0][1][r>>1]);clear(tot);return ret;
}
int main() {
// freopen("in.txt","r",stdin);int kase=read();while (kase--) {ans=0;n=read();for (register int i=1;i<=n;++i) a[i]=read();if (n&1) {smax(ans,calc_od(1,n-1)+a[n]);smax(ans,calc_ev(2,n)+a[1]);} else {smax(ans,calc_od(1,n));smax(ans,calc_ev(2,n-1)+a[1]);}cout<<ans<<endl;}return 0;
}