You are given an array aa consisting of nn integers.
Your task is to determine if aa has some subsequence of length at least 33 that is a palindrome.
Recall that an array bb is called a subsequence of the array aa if bb can be obtained by removing some (possibly, zero) elements from aa (not necessarily consecutive) without changing the order of remaining elements. For example, [2][2], [1,2,1,3][1,2,1,3] and [2,3][2,3] are subsequences of [1,2,1,3][1,2,1,3], but [1,1,2][1,1,2]and [4][4] are not.
Also, recall that a palindrome is an array that reads the same backward as forward. In other words, the array aa of length nn is the palindrome if ai=an−i−1ai=an−i−1 for all ii from 11 to nn. For example, arrays [1234][1234], [1,2,1][1,2,1], [1,3,2,2,3,1][1,3,2,2,3,1] and [10,100,10][10,100,10] are palindromes, but arrays [1,2][1,2] and [1,2,3,1][1,2,3,1] are not.
You have to answer tt independent test cases.
Input
The first line of the input contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases.
Next 2t2t lines describe test cases. The first line of the test case contains one integer nn (3≤n≤50003≤n≤5000) — the length of aa. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n), where aiai is the ii-th element of aa.
It is guaranteed that the sum of nn over all test cases does not exceed 50005000 (∑n≤5000∑n≤5000).
Output
For each test case, print the answer — "YES" (without quotes) if aa has some subsequence of length at least 33 that is a palindrome and "NO" otherwise.
Example
Input5 3 1 2 1 5 1 2 2 3 2 3 1 1 2 4 1 2 2 1 10 1 1 2 2 3 3 4 4 5 5OutputYES YES NO YES NO
简单的回文字符串,反序求最长公共子序列,如果能大于三就是yes,感觉可以在dp内判断是否大于三,可以尝试一下
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); int a[5001] = { 0 }; int b[5001] = { 0 }; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); b[n - i - 1 ] = a[i]; } int dp[5001][5001] = { 0 }; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (a[i] == b[j]) { dp[i + 1][j + 1] = dp[i][j] + 1; } else { dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]); } } } if (dp[n][n] >= 3) { printf("YES\n"); } else { printf("NO\n"); } } return 0; }