title: how to find longest palindromic subsequence?
body: <p>Here is the problem (6.7  <a href="http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf" rel="nofollow noreferrer">ch6</a> ) from Algorithms book (by Vazirani) that slightly differs from the classical problem that <a href="https://stackoverflow.com/questions/1115001/write-a-function-that-returns-the-longest-palindrome-in-a-given-string">finding longest palindrome</a>. How can I solve this problem ?</p>
  
  <blockquote>
    <p>A subsequence is palindromic if it is
    the same whether read left to right or
    right to left. For instance, the
    sequence</p>
  
  <pre><code>A,C,G,T,G,T,C,A,A,A,A,T,C,G
  </code></pre>
    
    <p>has many palindromic subsequences,
    including <code>A,C,G,C,A</code> and <code>A,A,A,A</code>
    (on the other hand, the subsequence
    <code>A,C,T</code> is not palindromic). Devise an
    algorithm that takes a sequence <code>x[1
    ...n]</code> and returns the (length of the)
    longest palindromic subsequence. Its
    running time should be <code>O(n^2)</code></p>
  </blockquote>