Ta có thể giải bài toán này với các thông tin mấu chốt sau:

• Vì lúc nào ta phải lấy chính xác ~3~ phần tử trong dãy, ta nên lấy nhiều nhất số lượng phần tử có thể, và chỉ để lại trong dãy ~(n \bmod 3)~ phần tử.

• Thay vì nghĩ đến việc cực đại hóa tổng các số có thể lấy được, ta có thể nghĩ đến việc tối thiểu hóa số lượng phần tử để lại trong dãy.

Vì số lượng phần tử để lại nhỏ (không quá 2 phần tử), ta có thể duyệt toàn bộ các phần tử để lại và tìm tổng nhỏ nhất của chúng.

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
long long A[MAXN];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long sum=0,ans=1e18;
        for(int i=1;i<=n;i++)
        {
            cin>>A[i];
            sum+=A[i];
        }
        if(n%3==0) ans=0;
        if(n%3==1) for(int i=1;i<=n;i+=3) ans=min(ans,A[i]);
        if(n%3==2) for(int i=1;i<=n;i+=3) for(int j=i+1;j<=n;j+=3) ans=min(ans,A[i]+A[j]);
        cout<<sum-ans<<"\n";
    }
}