Question $1$ A palindrome is a word, number, phrase, or other sequence of symbols that reads the same backwards as forwards, such as madam or racecar. A

subsequence is a palindrom problem is a longest subsequence in the sequence which is a palindrome. For instance, the sequence

ACGTGTC AAAATCG

has palindrom subsequences such as ACGCA and AAAA. Devise an algorithm that takes a sequence

$x_1{x}_{2}cdots{x}_n$

and returns the length of the longest palindrom subsequence. Compute the complexity of running time. Implement the algorithm in python.