时间限制:1 Sec 内存限制:64 MiB
提交
Reverie有一个长度为 n 的正整数数组 A, 她想从中挑出一些数字，使得这些数字的和最大，选中的任意两个数字在原数组中不能相邻。 你能帮帮她么？
Reverie有一个长度为 n 的正整数数组 A, 她想从中挑出一些数字，使得这些数字的和最大，选中的任意两个数字在原数组中不能相邻。
你能帮帮她么？
第一行一个正整数 T, 代表测试的组数。每组测试第一行一个正整数 n 表示数组的大小，第二行 n 个正整数表示数组里的数，以空格分隔。$1 \leq T\leq 100$$1 \leq n \leq 1000$$1 \leq A_i \leq 1000$
第一行一个正整数 T, 代表测试的组数。
每组测试第一行一个正整数 n 表示数组的大小，第二行 n 个正整数表示数组里的数，以空格分隔。
$1 \leq T\leq 100$
$1 \leq n \leq 1000$
$1 \leq A_i \leq 1000$
每组测试，一行内输出一个整数表示选出的数的和。
2 4 1 2 3 1 5 2 7 9 3 1
4 12