A subsequence is called palindromic if it results in the same sequence when read from left-to-right and right-to-left. For example, in the sequence: A, A,A, T,G, G,T, A,C, G,A
The subsequences A, A,A and A, T,G, G,T, A are palindromic, while A, C,G is not. Give an algorithm to find the length of the longest palindromic subsequence in a sequence a[1 ...n]. Your algorithm should run in O(n2) time. Show the proof of correctness and proof of running time, respectively.