子序列问题

题目描述:

我们称一个长度为\(k\)的整数序列\(C=c_1,c_2,\cdots,c_k\)是"好的"，如果其最小元素和最大元素的平均值等于其中位数。对于长度为\(k\)的序列，中位数定义为排序后第\(\lceil k/2 \rceil\)小的元素（\(\lceil x \rceil\)表示不小于\(x\)的最小整数）。例如：

•  序列1, 7, 4, 3 的中位数是3（排序后为1, 3, 4, 7）
•  序列5, 8, 2, 1, 6 的中位数是5（排序后为1, 2, 5, 6, 8）

形式化地说，设\(D=d_1,d_2,\cdots,d_k\)为\(C\)排序后的序列，则\(C\)是好的当且仅当：
\(
\frac{d_1 + d_k}{2} = d_{\lceil k/2 \rceil}
\)

给定一个整数序列\(A=a_1,a_2,\cdots,a_n\)，请计算其最长"好"子序列的长度。子序列是指通过删除原序列中某些元素（可以不删除）而不改变剩余元素顺序得到的新序列。

输入格式:

输入包含多组测试数据。第一行一个整数\(T\) \((1 \leq T \leq 10)\)表示测试用例数量。每组测试用例包含：

• 第一行：整数\(n\) \((1 \leq n \leq 3 \times 10^3)\)表示序列长度
• 第二行：\(n\)个整数\(a_i\) \((1 \leq a_i \leq 10^9)\)表示序列

保证所有测试用例的\(n\)之和不超过\(3 \times 10^4\)。

输出格式:

每组测试用例输出一个整数，表示最长"好"子序列的长度。

数据范围:

30%：\(n \leq 20, a_i \leq 100\)

60%：\(n \leq 100, a_i \leq 10^3\)

80%：\(n \leq 1000\)

100%：无特殊限制

样例输入:

4
7
3 5 9 8 2 11 5
7
7 9 2 4 17 10 15
1
100
2
100 100

样例输出:

5
4
1
2

提示:

对于第一个样例测试用例，最长的优质子序列是3,5,8,2,5。其最小元素为2，最大元素为8，中位数为5。

对于第二个样例测试用例，最长的优质子序列是7,9,4,10。其最小元素为4，最大元素为10，中位数为7。

时间限制: 2000ms
空间限制: 256MB

---

来源: 25年比赛小学组t5