Subsecuencia creciente más larga
En informática , el problema de subsecuencia creciente más largo es encontrar una subsecuencia de una secuencia dada en la que los elementos de la subsecuencia estén ordenados, de menor a mayor, y en la que la subsecuencia sea lo más larga posible. Esta subsecuencia no es necesariamente contigua o única. Las subsecuencias crecientes más largas se estudian en el contexto de varias disciplinas relacionadas con las matemáticas , incluida la algorítmica , la teoría de matrices aleatorias, la teoría de la representación y la física . [1] El problema de subsecuencia creciente más larga se puede resolver en el tiempo O( n log n), donde n denota la longitud de la secuencia de entrada. [2]
Esta subsecuencia tiene una longitud de seis; la secuencia de entrada no tiene subsecuencias crecientes de siete miembros. La subsecuencia creciente más larga en este ejemplo no es la única solución: por ejemplo,
El problema de la subsecuencia creciente más larga está estrechamente relacionado con el problema de la subsecuencia común más larga , que tiene una solución de programación dinámica de tiempo cuadrática : la subsecuencia creciente más larga de una secuencia S es la subsecuencia común más larga de S y T , donde T es el resultado de ordenar S . Sin embargo, para el caso especial en el que la entrada es una permutación de los números enteros 1, 2, ..., n , este enfoque se puede hacer mucho más eficiente, lo que lleva a límites de tiempo de la forma O( n log log n ). [3]
La camarilla más grande en un gráfico de permutación corresponde a la subsecuencia decreciente más larga de la permutación que define el gráfico (suponiendo que la secuencia original no permutada se ordena del valor más bajo al más alto). De manera similar, el conjunto independiente máximo en un gráfico de permutación corresponde a la subsecuencia no decreciente más larga. Por lo tanto, los algoritmos de subsecuencias crecientes más largas se pueden usar para resolver el problema de la camarilla de manera eficiente en gráficos de permutación. [4]
En la correspondencia de Robinson-Schensted entre permutaciones y cuadros de Young , la longitud de la primera fila del cuadro correspondiente a una permutación es igual a la longitud de la subsecuencia creciente más larga de la permutación, y la longitud de la primera columna es igual a la longitud de la más larga. subsecuencia decreciente. [2]
El algoritmo descrito a continuación resuelve el problema de la subsecuencia creciente más larga de manera eficiente con matrices y búsqueda binaria . Procesa los elementos de la secuencia en orden, manteniendo la subsecuencia creciente más larga encontrada hasta el momento. Denote los valores de secuencia como etc. Luego, después de procesar el algoritmo, tendrá valores almacenados en dos matrices:
![{\ estilo de visualización X [0], X [1], \ ldots,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee41a1f94997bce98913557706e9e14ca29ba91c)
![{\ estilo de visualización X [i],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecdde37a6ac98179222a6e2d4d827dab3b46cc05)
