Celle riempite
Confronti
Più lunga finora

  • In riempimento
  • Letta
  • Risposta

Di più sulla sottosequenza crescente più lunga

Sottosequenza crescente più lunga (LIS)

In una lista di numeri, quanti ne puoi scegliere, mantenendo il loro ordine, in modo che ognuno sia più grande del precedente? La sottosequenza crescente più lunga risponde a questa domanda. Scrivi una lista e guarda la programmazione dinamica calcolare, per ogni posizione, la catena più lunga che finisce lì. Premi Avvia per guardare la tabella riempirsi, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Scrivi una lista di numeri. Per ogni posizione la tabella contiene la lunghezza della catena crescente di valori più lunga che finisce lì, e la posizione precedente che essa prosegue. Spunta Consenti valori uguali per catene che non scendono mai. Alla fine la catena viene riletta a partire dal suo ultimo valore. Nuovo esempio crea un'altra lista. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

Come funziona

  1. Scrivi una lista di numeri, separati da virgole o spazi. Spunta Consenti valori uguali per catene che non scendono mai.
  2. Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi.
  3. Guarda ogni posizione confrontata con tutte quelle precedenti, poi vedi la catena più lunga riletta in arancione.

Come funziona la tabella

La tabella ha tre righe: i valori, la lunghezza della sottosequenza crescente più lunga che finisce in ogni posizione e la posizione che essa prosegue. Un valore da solo è una catena di lunghezza 1. Poi si controlla ogni posizione precedente: se il suo valore è più piccolo, la catena che finisce lì può essere allungata con questo valore, e la sua lunghezza cresce di uno. Vince l'allungamento più lungo, e la sua posizione va nella terza riga.

Rileggere la catena

La sottosequenza crescente più lunga finisce nella posizione con la lunghezza maggiore. Da lì, la terza riga dice quale posizione viene prima, e la terza riga di quella posizione dice quale viene ancora prima, fino a una posizione senza predecessore. Letti in ordine, quei valori sono la risposta. Con Consenti valori uguali spuntato, un valore può anche seguire un valore uguale, e si ottiene la catena più lunga che non scende mai.

Domande frequenti

Qual è la differenza tra una sottosequenza e un sottoarray?

Un sottoarray è un blocco di valori vicini. Una sottosequenza mantiene l'ordine ma può saltare dei valori, quindi in 3, 10, 2, 1, 20 i valori 3, 10 e 20 formano una sottosequenza crescente anche se 2 e 1 stanno in mezzo.

Quanto è veloce l'algoritmo LIS?

Il metodo della tabella confronta ogni coppia di posizioni: n·(n − 1)/2 confronti per n valori. Il patience sorting ci riesce in O(n log n): tiene, per ogni lunghezza, il valore più piccolo che chiude una catena di quella lunghezza, e colloca ogni nuovo valore con la ricerca binaria.

La sottosequenza crescente più lunga è unica?

Non sempre. In 1, 3, 2, 4 sia 1, 3, 4 sia 1, 2, 4 hanno lunghezza 3. La tabella dà la lunghezza, e la rilettura ne trova una.

Dove si usa la sottosequenza crescente più lunga?

Nel confronto di file e genomi, dove alcuni metodi trovano prima le righe corrispondenti e poi prendono una sottosequenza crescente delle loro posizioni; nella pianificazione e nei rompicapi di impilamento di scatole; e in matematica, dove la lunghezza della LIS di un mescolamento casuale è un famoso oggetto di studio.

Viene inviato qualcosa da qualche parte?

No. Tutto viene calcolato nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor