OIA-Wiki

Dadas dos secuencias de números, dar la secuencia más larga que sea subsecuencia de ambas.

Por ejemplo, dadas $A=\{20, 30, 23, 17, 20, 48, 29\}$ y $B=\{15, 20, 17, 30, 29\}$, la respuesta sería $\{20, 17, 29\}$ ó $\{20, 30, 29\}$.

Se recomienda pensarlo antes de avanzar a ver la solución. ... ...

Vamos a resolverlo con programación dinámica.

Voy a decir de una la asociación directa que se puede hacer con el problema de Máxima subsecuencia palindrómica. Algo que muchas veces sirve es llevar un problema a otro que ya conocemos (o conocemos mejor), y tratar de resolver ese segundo. Hay que estar segurísimos de que ambos problemas se pueden relacionar, y no hay ningún caso que nos estamos perdiendo, y listo.

Qué pasa si ponemos los conjuntos $A$ y $B$ uno al lado del otro, pero invertimos $B$? Llamemos $U$ de unión a este conjunto. Entonces una subsecuencia común va a estar en la mitad izquierda de esta unión, y va a estar invertida en la mitad derecha, dejándonos así una subsecuencia palindrómica.

En el ejemplo de arriba tendríamos $\{20, 30, 23, 17, 20, 48, 29, 29, 30, 17, 20, 15\}$, y se ve que está la subsecuencia palindrómica $\{20, 30, 30, 20\}$, por lo que $\{20, 30\}$ es una subs. común, y también está $\{20, 30, 29, 29, 30, 20\}$, por lo que $\{20, 30, 29\}$ es común.

Es fácil demostrar que este problema es equivalente al de LCS. Lo único con lo que hay que tener cuidado es que los palíndromos deben tener la misma cantidad de elementos de $A$ que de $B$. Si no, por ejemplo, si $A=\{1, 2, 1\}$ y $B=\{2\}$, tendríamos que $\{1, 2, 1, 2\}$ es un palíndromo presente al pegar $A$ con $B$ invertido, pero $1, 2$ no es una subsecuencia común.

Es fácil ver que si cumplimos con esto de agarrar la misma cantidad de elementos de cada conjunto, entonces tenemos la equivalencia del problema: cualquier subsecuencia común será un palíndromo en $U$, y un palíndromo con misma cantidad de elementos de $A$ y de $B$ de $U$ será una subsecuencia común de $A$ y $B$.

Una vez que tenemos esto, simplemente resolvemos el problema de la subsecuencia palindrómica en $O(n*m)$, donde $n$ es la longitud de $A$ y $m$ la de $B$, ya que el borde izquierdo del palíndromo iterará adentro de $A$ y el borde derecho deberá estar en $B$.