A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence

$A,C,G,T,G,T,C,A,A,A,A,T,C,G$

has many palindromic subsequences, including $A,C,G,C,$A and $A,A,A,A($on the other hand, the subsequence A$,$C$,$T is not palindromic$).$ Devise an algorithm that takes a sequence $x[1$dotsn$]$ and returns the $($length of the$)$ longest palindromic subsequence. Its ruming time should be $O(n^2).$