题目描述
小猫在研究序列。小猫在研究选择。
给定一个长度为N的序列a1,a2,…,aN，请你在这N个元素中选出一些（可以不选，可以全选），使得对于任意1≤i<N，ai与ai+1不被同时选，求选出的数的和最大是多少。
输入描述:
第一行一个正整数T，表示数据组数。每组数据的第一行一个正整数N。接下来一行N个正整数a1,a2,…,aN。
输出描述:
T行，每行一个整数，表示每组数据的答案。
示例1
输入
复制
3
5
1 100 101 100 1
4
1 2 3 4
3
51 100 51
输出
复制
200
6
102
备注:
1≤T,N,ai≤100
#include <iostream>
using namespace std;
int a[105], dp[105];
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
for(int i=0; i<n; i++)
cin>>a[i];
dp[0]=a[0];
dp[1]=max(a[0], a[1]);
for(int i=2; i<n; i++)
dp[i]=max(dp[i-1], dp[i-2]+a[i]);
cout<<dp[n-1]<<endl;
}
return 0;
}