Explicar el algoritmo para resolver el problema de la 'subsecuencia creciente más larga'

Question

He estado tratando de entender este algoritmo durante las últimas dos horas, pero parece que no puede obtenerlo. ¿Alguien puede explicarlo de manera fácil de entender?

function lis_length(a) 
    n := a.length 
    q := new Array(n) 
    for k from 0 to n: 
     max := 0; 
     for j from 0 to k, if a[k] > a[j]: 
      if q[j] > max, then set max = q[j]. 
     q[k] := max + 1; 
    max := 0 
    for i from 0 to n: 
     if q[i] > max, then set max = q[i]. 
    return max; 

Answer 1

Después de que termina el primer bucle (doble), q[i] es la longitud de la subsecuencia creciente más larga que termina en la posición i.

para ver cómo funciona el bucle doble, supongamos q[j] ya contenía la longitud de la subsecuencia más grande aumentando termina en la posición j, pero sólo para j entre 0 y k-1. Dado esto, ¿cómo calcularías q[k]?

Bueno, usted encontrará toda la j con j < k y a[j] < a[k], ver cuáles de los valores correspondientes q[j] era grande, agrega uno, y ese valor en STASH q[k]. Esto es exactamente lo que hace el lazo interno.

Por lo tanto, en la entrada al lazo interno, q[j] ya tiene los valores correctos para j entre 0 y k-1. Y a la salida, también tiene el valor correcto para k. Entonces, cuando el bucle doble sale, q[i] tiene el valor correcto para todos i entre 0 y n.

El ciclo final simplemente selecciona el mayor de ellos, que es la respuesta.

Answer 2

Para cada elemento de haz de la cuenta de subsecuencia más larga de elementos hechos con el elemento actual como incrementa en una longitud de subsecuencia más larga de los elementos anteriores elemento de corriente de tal manera que su valor más grande es menor que el valor de elemento actual.

El algoritmo toma una matriz de números positivos (no puede tener cero o menos como elemento).