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 , , , and (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 , your algorithm should return . What is the running time of your algorithm?
Let 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 , and then solve the longest common subsequence problem on and , possibly adding in an extra letter to account for palindromes with a central letter. Since there are places at which we could split the input word and the problem takes time , we can solve the palindrome problem in time .