Problema de la subsecuencia més llarga

En Ciències de la Computació, el problema de la subsecuencia creixent màxima consistix en trobar una subsecuencia d'una seqüència donada a on els elements de la subsecuencia estan ordenats, de menor a major, i la subsecuencia siga tan llarga com siga possible. Esta subsecuencia no és necessàriament contínua, o única. La subsecuencias creixents màximes són estudiades per vàries disciplines relacionades en les matemàtiques, incloent algoritmes, física i teories de matriu aleatòria. El problema de la subsecuencia creixent màxima és soluble en O(n log n), a on n denota el tamany de la seqüència d'entrada.

Eixemple

En els primers 16 térmens de la seqüència de Van der Corput binaria

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

una subsecuencia creixent màxima és

0, 2, 6, 9, 11, 15.

Esta subsecuencia té llongitut sis; la subsecuencia d'entrada no té subsecuencias creixents de tamany sèt. La subsecuencia creixent màxima en este eixemple no és única: per eixemple,

0, 4, 6, 9, 11, 15 o 0, 4, 6, 9, 13, 15

són atres subsecuencias creixent d'igual llongitut per a la mateixa subsecuencia d'entrada.

Relació en atres problemes algorítmics

El problema de la subsecuencia creixent màxima està estretament relacionat en el problema de subsecuencia comú més llarga, que té una solució de [[programació dinàmica]] en temps quadràtic: la subsecuencia creixent màxima d'una seqüència S és la subsecuencia comuna màxima de S i T, a on T és el resultat d'ordenar S. No obstant, per al cas especial en que l'entrada és una permutaciòn de sancers 1, 2, ..., n, esta proposta pot ser eixecutada molt més eficientemente , aplegant a un temps de la forma O(n log log n).

El clique major en un grafo de permutació està definit per la subsecuencia decreixent màxima de la permutació que definix al grafo; la subsecuencia decreixent màxima és equivalent en complexitat computacional, utilisat l'opost dels números d'entrada, a la subsecuencia creixent màxima. Aixina, els algoritmes de la subsecuencia creixent màxima poden ser usats per a resoldre el [[problema del clique]] eficientemente en permutation graphs.

En la correspondència Robinson–Schensted entre permutacionés i la taula de Young, la llongitut de la primera fila de la taula corresponent a la permutaciónes igual a la llongitut de la subsecuencia creixent més llarga de la permutació, i la llongitut de la primera columna és igual a la llongitut de la subsecuencia decreixent més llarga.

Vore també

• Problema de subsecuencia comú més llarga