Longest Palindromic Subsequence

Given a list of integers, your task is to find the length of the longest subsequence that is a palindrome.

A subsequence is a sequence derived from the original list by deleting zero or more elements without changing the order of the remaining elements. A sequence is a palindrome if it reads the same backward as forward.

This problem can be efficiently solved using dynamic programming. One common approach is to use a 2-dimensional DP array where dp[i][j] represents the length of the longest palindromic subsequence in the subarray from index i to j.

The recurrence relation is given by:

\(dp[i][j]=\begin{cases}1&\text{if } i=j,\\ 2&\text{if } arr[i]=arr[j] \text{ and } j=i+1,\\ dp[i+1][j-1]+2&\text{if } arr[i]=arr[j],\\ \max(dp[i+1][j],dp[i][j-1])&\text{if } arr[i]\neq arr[j].\end{cases}\)

inputFormat

The input is read from standard input (stdin) and consists of two lines.

• The first line contains a single integer n, representing the number of elements in the list.
• The second line contains n space-separated integers representing the elements of the list.

outputFormat

Output to standard output (stdout) a single integer representing the length of the longest palindromic subsequence in the list.

## sample

6
1 2 3 2 1 4

5

</p>