Finding the longest substring by dynamic programmin

Question

A palindrome is a string that is the same as its reverse. The following strings are examples of palindromes: abba, refer, 0101010, x. A substring of a string X = x1, x2, x3, . . . , xn is a string Y = y1, y2, . . . , yk such that y1 = xi1 , y2 = xi2 , . . . , yk = xik and i1 < i2 < . . . ik.

For example, 2, 7, 4 is a substring of 1, 2, 8, 7, 4. Design the most efficient dynamic programming algorithm that you can that inputs a string X of length n and finds the length of the longest substring of X that is a palindrome. Can this problem be solved in O(n^2) time?

Answer 1

This is incase of substring. But your example in your question is indicating a subsequence. The O(n^2) solution will be something like this- len(l,r)- the length of longest palindrome substring of x[l..r].

for i=1 to n
 for j=1 to n
  if(i=j) 
    len(i,j)=1       //1-length palindromes
  if(i+1=j)
     then len(i,j)=2 if (x[l]=x[r]),or 1 otherwise //for even-length palindrome. 
  if(x[l]=x[r]) 
     then len(i,j)=2+len(i+1,j-1) //both character same
  else
     len(l,r)=maximum(len(l,r-1),len(l+1,r)); //increase left,decrease right

The answer is len(1,n) which will be found in O(n^2) time.