Solución:
Esto se puede resolver en O (n ^ 2) usando programación dinámica. Básicamente, el problema es construir la subsecuencia palindrómica más larga en x[i...j] usando la subsecuencia más larga para x[i+1...j], x[i,...j-1] y x[i+1,...,j-1] (si la primera y la última letra son iguales).
En primer lugar, la cadena vacía y una cadena de un solo carácter es trivialmente un palíndromo. Observe que para una subcadena x[i,...,j], si x[i]==x[j], podemos decir que la longitud del palíndromo más largo es el palíndromo más largo sobre x[i+1,...,j-1]+2. Si no coinciden, el palíndromo más largo es el máximo del de x[i+1,...,j] y y[i,...,j-1].
Esto nos da la función:
longest(i,j)= j-i+1 if j-i<=0,
2+longest(i+1,j-1) if x[i]==x[j]
max(longest(i+1,j),longest(i,j-1)) otherwise
Simplemente puede implementar una versión memorizada de esa función o codificar una tabla de[i][j] de abajo hacia arriba.
Esto le da solo la longitud de la subsecuencia más larga, no la subsecuencia real en sí. Pero también se puede ampliar fácilmente para hacer eso.
Este problema también se puede resolver como una variación de un problema muy común llamado problema LCS (subsecuencia común más larga). Deje que la cadena de entrada esté representada por una matriz de caracteres s1[0…n-1].
1) Invierta la secuencia dada y almacene la inversa en otra matriz, digamos s2[0..n-1] que en esencia es s1[n-1….0]
2) LCS de la secuencia dada s1 y la secuencia inversa s2 será la secuencia palindrómica más larga.
Esta solución también es una solución O (n ^ 2).