Sottosequenza crescente più lunga
DP O(n^2), poi il trucco O(n log n)
Sottosequenza crescente più lunga è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos'è una LIS
Una sottosequenza mantiene l'ordine ma salta alcuni elementi. La più lunga crescente è la più lunga tra queste sequenze che cresce strettamente.
a = [3, 1, 4, 1, 5, 9, 2]Sottosequenza, non sottoarray
A differenza di un sottoarray, una LIS non deve essere contigua. È possibile saltare numeri più piccoli per mantenere la catena crescente.
Lo stato DP O(n^2)
Definisca dp[i] come la lunghezza della LIS che termina all'indice i. Ogni elemento costituisce da solo almeno una sottosequenza di lunghezza uno.
dp = [1] * nLa transizione O(n^2)
Per ogni i, esamini ogni j precedente. Se a[j] è più piccolo, estenda la sequenza: dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)Leggere la risposta
Il risultato è il valore più grande nella tabella, perché la LIS può terminare ovunque, non solo all'ultimo indice.
answer = max(dp)Perché O(n^2) può causare TLE
Il doppio ciclo costa O(n^2). Per n vicino a 100000 è decisamente troppo lento e produce un verdetto di time-limit.
L'idea del patience sorting
Il metodo più veloce mantiene una lista con la coda minima possibile per ogni lunghezza di sottosequenza, come nel patience sorting.
tails = []Usare bisect per inserire
Per ogni numero, cerchi con una ricerca binaria la posizione in cui inserirlo tra le code usando bisect_left, per un totale di O(n log n).
from bisect import bisect_leftEstendere o sostituire
Se la posizione è oltre la fine, usi append per allungare la LIS. Altrimenti sostituisca quella coda con il valore più piccolo.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xLa lunghezza è in tails
Al termine della scansione, len(tails) è la lunghezza della LIS. La lista in sé non è sempre la sottosequenza; è esatta soltanto la sua lunghezza.
answer = len(tails)Strettamente crescente e non decrescente
Per la variante non decrescente, passi a bisect_right così i valori uguali possono estendere la catena.
from bisect import bisect_rightVerifica rapida
Quale metodo trova la lunghezza della LIS in O(n log n)?
Riepilogo: da n^2 a n log n
Ora è in grado di risolvere la LIS in due modi. La DP O(n^2) è semplice; il metodo basato su tails e bisect funziona anche con input grandi e supera il limite di tempo.
Domande Frequenti
La lezione «Sottosequenza crescente più lunga» è gratuita?
Sì — il testo completo di «Sottosequenza crescente più lunga» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Sottosequenza crescente più lunga»?
DP O(n^2), poi il trucco O(n log n) Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Sottosequenza crescente più lunga»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Memoization e tabulation a confronto
- Definire stato e transizione
- Salita delle scale e combinazioni di monete
- Sottosequenza crescente più lunga