This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N]; //原始数组
int f[N]; //递推结果数组
/*
记忆化搜索
状态转移方程是 前i个数 = max(前i-1个数，前i-2个数 +第i个数)
平时写一下搜索还是挺好的。 (比Dp还快 2ms)
O(n)
*/
int dfs(int u) {
if (u <= 0) return 0;//注意一下这个边界
if (f[u]) return f[u];//记忆化搜索的灵魂
return f[u] = max(dfs(u - 1), dfs(u - 2) + a[u]);
}
int main() {
int T, n;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
//每次重置一下结果数组
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
printf("%d\n", dfs(n));
return 0;
