15-2 Longest palindrome subsequence

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 11, civic\text{civic}, racecar\text{racecar}, and aibohphobia\text{aibohphobia} (fear of palindromes).

Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input character\text{character}, your algorithm should return carac\text{carac}. What is the running time of your algorithm?

Let A[1..n]A[1..n] denote the array which contains the given word. First note that for a palindrome to be a subsequence we must be able to divide the input word at some position ii, and then solve the longest common subsequence problem on A[1..i]A[1..i] and A[i+1..n]A[i + 1..n], possibly adding in an extra letter to account for palindromes with a central letter. Since there are nn places at which we could split the input word and the LCS\text{LCS} problem takes time O(n2)O(n^2), we can solve the palindrome problem in time O(n3)O(n^3).