3672 - Palindrome

[ymondelo20]

http://coj.uci.cu/24h/problem.xhtml?pid=3672

[isaac]

Si se quiere obtener el mayor palindrome que es subsecuencia de una cadena dada, bastaria con realizar un LCS entre la cadena y ella misma, pero invertida. Como esto nos da la longitud del mayor palindrome que existe en la cadena, bastaria con restarle al total de caracteres de la cadena, la longitud del LCS antes mencionado, lo que representa la cantidad de caracteres que no pertenecen al palindrome y deben ser agregados para emparejar la situacion y formar un palindrome. En resumen, seria N - LCS(cadena, cadena_invertida)