D. Maximum Sum on Even Positions

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define INF 4e18

const int N = 2e5 + 10;
ll Memo[N][3][2];
int n ,a[N];

ll calc(int i ,int tk ,bool flag){
    if( i == n ){
        if( tk == 1 )
            if( flag )
                return -INF;
        return 0;
    }

    ll &Re = Memo[i][tk][flag];
    if( Re != -1ll ) return Re;

    ll Res = 0ll;
    if( tk == 0 ) {
        Res = calc(i + 1 ,0 ,0) + (i % 2 == 0) * a[i];
        Res = max(Res ,calc(i + 1 ,1 ,1) + (i % 2 == 1) * a[i]);
    } else if( tk == 1 ) {
        Res = calc(i + 1 ,1 ,!flag) + (i % 2 == 1) * a[i];
        if( flag == 0 ) /// --- \EvenLenOfRev --- ///
            Res = max(Res ,calc(i + 1 ,2 ,flag) + (i % 2 == 0) * a[i]);
    } else if( tk == 2 )
        Res = calc(i + 1 ,2 ,flag) + (i % 2 == 0) * a[i];

    return Re = Res;
}

void Solve() {
    scanf("%d" ,&n);
    for(int i=0 ; i<n ; i++)
        scanf("%d" ,&a[i]);

    for(int i=0 ; i<n ; i++)
        for(int j=0 ; j<3 ; j++)
            for(int k=0 ; k<2 ; k++)
                Memo[i][j][k] = -1ll;

    ll Ans = calc(0 ,0 ,0);
    printf("%I64d\n" ,Ans);
}

int main() {
    int Tc; scanf("%d" ,&Tc);
    while( Tc-- ) Solve();
    return 0;
}