Problem 2. Purpose: practice algorithm design using
dynamic programming. 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). Assume you are given a
sequence x[1...n] of characters. Denote L(i,j) the length of the
longest palindrome in the substring x[i,...,j]. The goal of the
Maximum Palindromic Subsequence Problem (MPSP)...