OIA-Wiki

Dada una secuencia de caracteres, encontrar la subsecuencia creciente más larga (denominada LIS, “longest increasing subsequence” por su traducción al inglés). Una subsecuencia es el conjunto de números que resulta de eliminar algunos de la secuencia inicial, sin modificar el orden.

Por ejemplo, en la secuencia $\{1, 4, 2, 3, 8, 5, 6\}$, una subsecuencia creciente es $1, 4, 8$, pero la más larga es $1, 2, 3, 5, 6$.

Recomendamos pensar primero una solución antes de pasar a leerla. ... ...

Vamos a utilizar programación dinámica. Vamos a ir de izquierda a derecha, y el estado que vamos a guardar es “cuál la subsecuencia creciente más larga que termina en la posición $i$”. Entonces, esta respuesta para la posición $i$, simplemente va a depender de las respuestas para posiciones anteriores, ya que si termina en $i$ no importan los números de después.

Y cómo hacemos para calcular entonces la subsecuencia más larga terminada en $i$, teniendo los valores para todas las posiciones anteriores? Bueno, vamos a ver los candidatos a “penúltimo”, que puede ser cualquiera de los anteriores, siempre y cuando la condición de que sea creciente no se pierda.

Entonces, simplemente vamos a mirar las posiciones $j=0, 1, \ldots, i-1$, y si el número de la posición $j$ es menor a la de $i$, una subsecuencia terminando en $i$ podría ser una que termina en la $j$, y agregarle la posición $i$. Entonces de los posibles $j$ como penúltimo, nos interesa guardar la posición que tiene la subsecuencia más larga terminando en él. Y a ese valor le sumamos uno por la posición $i$.

LIS.cpp

int main(){
    int n; // cantidad de numeros
    vector<int> nums;
    // se ingresan los nums
    int maxLongitud=1;
    vector<int> dp(n, 1); // con el número i nos garantizamos longitud 1 por lo menos en todas las posiciones
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            if(nums[j]<=nums[i]){ // Aca podriamos poner menor si quisieramos que sea estrictamente creciente, es decir, no permitir que {1, 3, 3, 4} valga.
                dp[i]=max(dp[i], dp[j]+1);
            }
        }
        maxLongitud=max(maxLongitud, dp[i]);
    }
    cout<<"La subsecuencia creciente mas larga tiene longitud: "<<maxLongitud<<endl;
}

Una vez que calculamos la longitud, cómo podemos hacer para reconstruir la subsecuencia más larga?

Otra vez, sugerimos pensar esto antes de avanzar. ... ...

Es sencillo, simplemente cuando vamos a actualizar $dp[i]$ por un valor más grande, guardamos en un vector $antecesor[i]$ la posición que estamos mirando como penúltima. Entonces después del

if(nums[j]<=nums[i])

queda:

if(dp[j]+1>dp[i]){
    dp[i]=dp[j]+1;
    antecesor[i]=j;
}

Para obtener la ultimo posicion de la subsecuencia haríamos

if(dp[i]>maxLongitud){
    end=i;
    maxLongitud=dp[i];
}

Y para imprimir la subsecuencia:

vector<int> subsecuencia;
while(end!=-1){
    subsecuencia.push_back(nums[end]);
    end=antecesor[end]; // con antecesor inicializada en -1 para que corte el while
}
 
reverse(subsecuencia.begin(), subsecuencia.end());
for(int i=0; i<maxLongitud; i++){
    cout<<subsecuencia[i];
    if(i<maxLongitud-1)cout<<", ";
}