algorithm - how to find longest palindromic subsequence?

Question

Here is the problem (6.7 ch6 ) from Algorithms book (by Vazirani) that slightly differs from the classical problem that finding longest palindrome. How can I solve this problem ?

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 ...n] and returns the (length of the) longest palindromic subsequence. Its running time should be O(n^2)

Answer 1

This can be solved in O(n^2) using dynamic programming. Basically, the problem is about building the longest palindromic subsequence in x[i...j] using the longest subsequence for x[i+1...j], x[i,...j-1] and x[i+1,...,j-1] (if first and last letters are the same).

Firstly, the empty string and a single character string is trivially a palindrome. Notice that for a substring x[i,...,j], if x[i]==x[j], we can say that the length of the longest palindrome is the longest palindrome over x[i+1,...,j-1]+2. If they don't match, the longest palindrome is the maximum of that of x[i+1,...,j] and y[i,...,j-1].

This gives us the function:

longest(i,j)= j-i+1 if j-i<=0,
              2+longest(i+1,j-1) if x[i]==x[j]
              max(longest(i+1,j),longest(i,j-1)) otherwise

You can simply implement a memoized version of that function, or code a table of longest[i][j] bottom up.

This gives you only the length of the longest subsequence, not the actual subsequence itself. But it can easily be extended to do that as well.

---