Massima sottosequenza crescente

In informatica, il problema della massima sottosequenza crescente consiste nel trovare una sottosequenza di una sequenza data in cui gli elementi della sottosequenza siano ordinati dal minore al maggiore e la cui lunghezza sia la massima possibile. La sottosequenza non deve essere necessariamente contigua, o univoca. Il problema della massima sottosequenza crescente è risolvibile in tempo O(n log n), dove n rappresenta la lunghezza della sequenza originale.

Esempio

Nei primi 16 termini della sequenza di Van der Corput

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

una delle massime sottosequenze crescenti è

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

Questa sottosequenza è lunga sei elementi; la sequenza originale non ha sottosequenze crescenti di lunghezza 7 o più. La massima sottosequenza crescente in questo caso non è unica: per esempio,

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

Sono altre sottosequenze crescenti della stessa lunghezza e dunque altre valide soluzioni per il problema in questo caso.

Limiti sulla lunghezza

Secondo il teorema di Erdős–Szekeres, ogni sequenza di n²+1 interi distinti ha una sottosequenza crescente o decrescente di lunghezza n + 1.