状态机模型
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int f[N][2];// 0 不行窃 1 行窃
int a[N];
int main()
{
int t,n;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
//f[i][0] 前i天中第i天不行窃 可以获得的最大价值
f[i][0] = max(f[i-1][0],f[i-1][1]);
//f[i][1] 前i天中第i天行窃 可以获得的最大价值
f[i][1] = f[i-1][0]+a[i];
}
cout<<max(f[n][0],f[n][1])<<endl;
}
return 0;
}