• Statements

  Dzy and Fox have a sequence A consisting of N numbers [A₁...A_N]. Dzy starts by taking the first number, then Fox takes the second number, then Dzy takes the third number and so on, they continue taking turns until all of the N numbers are taken. The player with the highest sum of numbers wins.

  Since Dzy is your dear friend, you decided to rotate the sequence (you may rotate it as many times as you like) in order to maximize Dzy's sum of numbers.

  Rotation is defined as removing the first element from the beginning of the sequence and adding it to the end of the sequence.

  So given the sequence A , you have to help Dzy and let him achieve the maximum possible sum.

1 5 1 5 3 2 4

12

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int MAXN = 1e4 + ;

int num[MAXN];

typedef long long LL;

int main(){

    int T, N;

    scanf("%d", &T);

    while(T--){

        scanf("%d", &N);

        LL sum = , cur;

        if(N == ){

            scanf("%lld", &cur);

            printf("%lld\n", cur);

            continue;

        }

        for(int i = ; i < N; i++){

            scanf("%d", num + i);

            sum += num[i];

        }

        if(N %  == ){

            cur = ;

            for(int i = ; i < N; i+= )

                cur += num[i];

            printf("%lld\n", max(cur, sum - cur));

        }

        else{

            LL sum1 = , sum2 = , cur1 = , cur2 = ;

            for(int i = ; i < N; i++){

                if(i %  == )

                    sum1 += num[i];

                else

                    sum2 += num[i];

            }

            LL ans = sum1;

            for(int i = ; i < N; i++){

                if(i % == )

                    cur1 += num[i];

                else

                    cur2 += num[i];

                if(i %  == ){

                    ans = max(ans, sum2 - cur2 + cur1);

                //    printf("%lld\n", sum2 - cur2 + cur1);

                }

                else{

                    ans = max(ans, sum1 - cur1 + cur2);

                //    printf("%lld\n", sum1 - cur1 + cur2);

                }

            }

            printf("%lld\n", ans);

        }

    }

    return ;

}