原题是 [ARC092E] Both Sides Merger。
Key observation：每个元素的下标奇偶性不改变。
于是讨论最后一个数是下标为奇数还是偶数加起来的数。将下标奇偶性相同的元素分开考虑。对于下标奇偶性相同的元素，不难发现答案的上界是所有 \(> 0\) 的元素之和（没有 \(> 0\) 的元素时选一个最大的），并且一定能够构造方案以达到上界。
例如，下面 O 代表对答案有贡献的元素，. 代表没有贡献的元素：
.O.O...O
方案是 .O.O...O \(\to\) O.O...O \(\to\) O...O \(\to\) O.O \(\to\) O。
于是分下标奇偶性排序一遍从大到小取即可。复杂度 \(O(n \log n)\)。
code
// Problem: C. Particles
// Contest: Codeforces - Codeforces Round 884 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1844/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n, a[maxn], b[maxn], c[maxn];
void solve() {
scanf("%lld", &n);
int t1 = 0, t2 = 0;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
if (i & 1) {
b[++t1] = a[i];
} else {
c[++t2] = a[i];
}
}
if (n == 1) {
printf("%lld\n", a[1]);
return;
}
ll s1 = 0, s2 = 0;
sort(b + 1, b + t1 + 1, greater<ll>());
sort(c + 1, c + t2 + 1, greater<ll>());
for (int i = 1; i <= t1; ++i) {
if (i > 1 && b[i] < 0) {
break;
}
s1 += b[i];
}
for (int i = 1; i <= t2; ++i) {
if (i > 1 && c[i] < 0) {
break;
}
s2 += c[i];
}
printf("%lld\n", max(s1, s2));
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}