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 n2+1 interi distinti ha una sottosequenza crescente o decrescente di lunghezza n + 1.
