Considere que B es una secuencia de símbolos de agrupación (,), [,], {y}. B se llama una secuencia equilibrada si tiene una longitud 0 o B tiene una de las siguientes formas: {X} Y o [X] Y o {X} Y donde X e Y se equilibran ellos mismos. Ejemplo para equilibrado: () - {[] ()} [] - ...

Ahora la pregunta es encontrar un algoritmo eficiente para encontrar la subsecuencia balanceada de longitud máxima (no necesariamente contigua) de una entrada dada que es una cadena de estos símbolos de agrupación.

Por ejemplo, si la entrada es() {([)] {(])}} [] , una de las subsecuencias de longitud máxima es() {[] {()}} []

Estoy casi seguro de que la solución es DP, pero de todos modos lo resuelvo y encuentro ejemplos en los que mi algoritmo no funciona. Solo estoy seguro de un enfoque, que es una combinación de DP y Divide and Conquer. Pero no es eficiente porque de todos modos la parte de D&C va a resolver algunos problemas superpuestos una y otra vez.