/*hud4512
dp[i]表示当前以下标i结束的最长公共上升子序列。 我们让第一个序列为原序列，第二个序列为原系列的反向。 则，也就是说，第二个序列的顺序为原序列的下标[n-1,0]，设为j 当j枚举到k时，对于dp[0] ~ dp[k-1]，都可以得到原序列的一个长度为2*dp[i]的题目要求的子序列。 可是对于，dp[k]，我们怎么判断此时，两个序列是否存在交集呢？假如存在交集，此时题目要求的子序列长度为2*dp[k] - 1 这样考虑，假如此时的序列没有交集，则此时两个序列的最长公共上升子序列，在序列二中的起始坐标必然不是k 那么它必然在j=[k+1,n-1]的时候已经出现过，并以dp[k]*2更新过ans 也就是说根本不用考虑嘛。。。直接将用dp[k]*2-1更新ans，答案并不会有错 PS:原序列和反序列的公共部分不一定都是回文，你所找的最长公共子序列一定是最开始找到的
你找到的不是回文的子序列长度一定不大于是回文的
所以说你只要长度
直接输出没问题
你要序列
只找第一个就行
只要保证一个在前面一个在后面
两个匹配的
后面的不超过前面的
所以有了k
/*hud4512*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = ;
int a[maxn], b[maxn];
int dp[maxn];
int max(int a,int b)
{
if(a>b) return a;
return b;
}
int solve(int n,int m)
{
memset(dp,,sizeof(dp));
int ans = ;
for(int i =; i<=n; i++)
{
int tmp = ;
for(int j =; j<=(n-i+); j++)//保证两个序列没有交集，不能遍历到m1 3 2 1 3就是反例
{
if(a[i] > b[j])
tmp = max(tmp,dp[j]);
else if(a[i] == b[j])
dp[j] = max(dp[j],tmp+);
if(j<(n-i+)) ans = max(ans, dp[j]*);
else ans = max(ans, dp[j]*-);//那么说明j是中点
}
}
return ans;
} int main()
{
int T;
int n;
scanf("%d",&T);
while(T--)
{
scanf("%d", &n);
for(int i = ,j=n; i <= n; i++,j--)
{
scanf("%d", &a[i]);
b[j] = a[i];
}
printf("%d\n",solve(n,n));
}
return ;
}