title: Massima sottosequenza crescente
text: # 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^2+1$ interi distinti ha una sottosequenza crescente o decrescente di lunghezza n + 1.
  
  