Longest Palindromic Subsequence

Our goal is to find the longest palindromic subsequence in a given sequence. For example, we are given a sequence "ABCBAD". The longest palindromic subsequence is "ABCBA". Now let $s$ is the given sequence  and we use $s[i]$ to denote the $i^\text{th}$ character in $s$. In addition, we let $L[i, j]$ denote the length of longest palindromic subsequence in $s[i:j]$ (from $s[i]$ to $s[j]$). If $s[i:j]$ is palindromic, then the front character $s[i]$ and the last character $s[j]$ should be the same. We can also say that:

$$L[i, j] = L[i+1, j-1] + 2$$

On the other hand, if $s[i:j]$ is not palindromic (or, $s[i]\neq s[j]$), then:

$$L[i, j] = max(L[i+1, j], L[i, j-1])$$

We can follow this rule to solve this problem recursively. First, we can consider the longest palindromic subsequence when $i=j$:

Because the length of $s[i:j]$ is 1, $L[i, j]=1$. Next, we consider $j = i+1$. $L[i, j]$ will be 2 only when $s[i]=s[j]$; otherwise, $L[i, j]=1$.

Next $j = i+2$ is considered. We can determine the value of $L[i, j]$ through the rules we just mentioned:

We can observe that when $i=1, j=3$, $s[i]=s[j]$, and thus $L[1, 3]=L[2, 2]+2=3$. We can repeatedly apply this process until $L[5, 5]$ is obtained:

We can create another table to store the $(i, j)$ index pair in the same way in order to obtain the sequence "ABCBA". Note that the time complexity of this algorithm is $O(n^2)$ and the space complexity is $O(n^2)$ as well.