Longest Increasing Subsequence

Q: Qual è la complessità temporale della sottosequenza crescente più lunga?

Il metodo tails richiede un tempo di O(n log n) e uno spazio di O(n) : una ricerca binaria per elemento. La tabella di programmazione dinamica su ogni coppia di indici richiede un tempo di O(n²) , mentre provare ogni sottosequenza richiede O(2ⁿ) . Per n = 2500 , si tratta di circa 30.000, 3 milioni e un numero astronomico di passaggi.

Q: Perché il metodo di ordinamento per pazienza restituisce la lunghezza corretta?

Dopo ogni elemento, tails[k] contiene il valore più piccolo con cui può terminare qualsiasi sottosequenza crescente di lunghezza k+1 vista finora. L'aggiunta avviene solo quando x è maggiore di ogni valore finale, il che significa che ora esiste una sottosequenza più lunga di una unità rispetto a qualsiasi sottosequenza precedente. La sostituzione non cambia mai la lunghezza, abbassa solo un valore finale, quindi la lunghezza della lista è sempre la lunghezza della sottosequenza crescente più lunga.

Q: Come si ottiene la sottosequenza crescente più lunga effettiva, non solo la sua lunghezza?

Registra un genitore per ogni elemento. Nella tabella O(n²) , il genitore di i è il j che ha assegnato il suo valore a ending[i] . Nel metodo tails, memorizza l'indice dell'elemento dietro ogni coda e, quando un elemento viene inserito, imposta il suo genitore sull'indice memorizzato una posizione alla sua sinistra. Poi risali i genitori partendo dalla fine della sottosequenza più lunga e inverti il risultato.

Q: Come si trova invece la sottosequenza non decrescente più lunga?

Consenti valori adiacenti uguali. Nella tabella, usa nums[j] ≤ nums[i] . Nel metodo delle code, cerca la prima coda strettamente maggiore di x invece che maggiore o uguale, così un valore uguale estende la lista anziché sostituire una coda. [7, 7, 7, 7] restituisce quindi 4.

MedioProgrammazione dinamica Ricerca binaria

+10

Ti viene fornita una lista di interi nums. Una sottosequenza mantiene alcuni elementi nell’ordine originale e scarta gli altri; gli elementi mantenuti non devono essere necessariamente adiacenti. Restituisci la lunghezza della sottosequenza più lunga i cui valori aumentano strettamente da sinistra a destra. Due valori uguali consecutivi non contano come un aumento.

Funzione

lengthOfLIS(nums: integer-array) → integer

numsinteger-array: l'elenco di interi da cui scegliere
Restituisceinteger: la lunghezza della sottosequenza strettamente crescente più lunga

Vincoli

1 ≤ nums.length ≤ 2500
-10⁴ ≤ nums[i] ≤ 10⁴

Esempi

Input: nums = [3, 1, 8, 2, 5, 9, 4, 7]
Output: 4
Spiegazione: Mantenendo 1, 2, 5, 9 si ottiene una sottosequenza crescente di lunghezza 4, così come con 1, 2, 5, 7 e 1, 2, 4, 7. Non è possibile scegliere cinque valori che continuino a crescere, quindi la risposta è 4.

+20 test nascosti all’invio

Per approfondire

Puoi restituire una delle sottosequenze crescenti più lunghe, non solo la sua lunghezza, e impiegare comunque un tempo O(n log n)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Una sottosequenza può saltare qualsiasi elemento, quindi una lista di n numeri ne ha 2^n, decisamente troppe da controllare. La soluzione con la programmazione dinamica consiste nel porre una domanda più circoscritta per ogni indice: quanto è lunga la migliore sottosequenza crescente che termina esattamente qui? Si ottiene così una tabella O(n²). La versione più veloce mantiene un numero per ogni lunghezza: il valore più piccolo con cui può terminare una sottosequenza di quella lunghezza, e inserisce ogni nuovo elemento con una ricerca binaria.

Prendi o salta ogni elemento

Corretto, ma non termina sui test più grandi

Intuizione

Scorri la lista e prendi una decisione per ogni elemento: tenerlo oppure escluderlo. Puoi tenere nums[i] solo quando è maggiore dell’ultimo valore che hai tenuto. Una funzione ricorsiva longest(i, prev) risponde alla domanda: se l’ultimo elemento tenuto si trova all’indice prev (oppure -1 se non hai ancora tenuto nulla), quanti altri elementi puoi aggiungere a partire dall’indice i?

Escludere dà longest(i+1, prev). Tenerlo, quando è consentito, dà 1 + longest(i+1, i). La risposta è il maggiore tra i due valori e, oltre la fine della lista, non si può aggiungere altro, quindi il risultato è 0. Ogni sottosequenza crescente corrisponde a un percorso di scelte tra tenere ed escludere, quindi la ricerca non può tralasciare quella migliore.

È lento perché entrambi i rami restano aperti ogni volta che i valori aumentano. In una lista come 1, 2, 3, ..., n le chiamate raddoppiano a ogni elemento: 2 elevato alla potenza di 40 corrisponde già a circa 10^12 chiamate, e i test più grandi hanno 2500 elementi. Eppure longest(i, prev) dipende solo dalla coppia (i, prev), quindi ci sono al massimo n² domande diverse. Porre ciascuna domanda una sola volta è il prossimo approccio.

Algoritmo

Scrivi longest(i, prev), dove prev è l’indice dell’ultimo elemento mantenuto, oppure -1.
Se i è oltre la fine, restituisci 0.
Salta nums[i]: best = longest(i+1, prev).
Se prev è -1 oppure nums[i] > nums[prev], mantienilo: best = max(best, 1 + longest(i+1, i)).
Restituisci best. La risposta è longest(0, -1).

def lengthOfLIS(nums):
    def longest(i, prev):
        # The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
        # prev is -1 while nothing has been taken.
        if i == len(nums):
            return 0
        best = longest(i + 1, prev)  # skip nums[i]
        if prev == -1 or nums[i] > nums[prev]:
            best = max(best, 1 + longest(i + 1, i))  # take nums[i]
        return best

    return longest(0, -1)

Sottosequenza più lunga che termina a ciascun indice

Intuizione

Stato. Sia ending[i] la lunghezza della sottosequenza crescente più lunga il cui ultimo elemento è nums[i]. Fissare l’ultimo elemento è ciò che permette di suddividere nettamente il problema: una volta che sai dove termina una sottosequenza, sai quali valori successivi possono seguirla.

Relazione di ricorrenza. Se la sottosequenza che termina in nums[i] ha più di un elemento, quello che precede nums[i] è un certo nums[j] con j < i e nums[j] < nums[i], e la parte che termina lì dovrebbe essere il più lunga possibile. Quindi ending[i] = 1 + max(ending[j]) per quei valori di j. Caso base: ogni elemento da solo è una sottosequenza, quindi ending[i] parte da 1. Ordine: ending[i] legge solo indici minori, quindi calcolalo da sinistra a destra.

Per [3, 1, 8, 2, 5, 9, 4, 7] la tabella è [1, 1, 2, 2, 3, 4, 3, 4]. Per esempio, 5 può seguire 3, 1 o 2, e la migliore di queste possibilità è 2, con ending = 2, quindi ending[4] = 3. La risposta è il valore più grande, 4, non l’ultimo: la sottosequenza migliore può terminare ovunque.

Ogni indice considera una volta ciascun indice precedente, quindi il lavoro consiste in n(n-1)/2 confronti, circa 3.1 × 10^6 per n = 2500.

Algoritmo

Crea ending con ogni elemento impostato a 1.
Per ogni i da sinistra a destra, esamina ogni j < i.
Se nums[j] < nums[i], imposta ending[i] su ending[j] + 1 quando questo valore è maggiore.
Restituisci il valore più grande in ending.

def lengthOfLIS(nums):
    n = len(nums)
    # ending[i]: the longest increasing subsequence that ends with nums[i]
    ending = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
                ending[i] = ending[j] + 1
    return max(ending)

Coda più corte con la ricerca binaria

Intuizione

La tabella qui sopra ricorda una lunghezza per ogni indice. Puoi ricordare meno: per ogni lunghezza, solo il valore più piccolo con cui può terminare una sottosequenza crescente di quella lunghezza. Chiamalo tails[k] per la lunghezza k+1. Un valore finale più piccolo è sempre almeno altrettanto valido, perché qualsiasi valore che può seguire una sottosequenza che termina con 9 può seguire anche una che termina con 5.

tails è sempre ordinato in ordine strettamente crescente: una sottosequenza di lunghezza k+2 che termina con t contiene una sottosequenza di lunghezza k+1 che termina con un valore minore di t. Quindi, per ogni nuovo valore x, cerca con la ricerca binaria il primo valore finale che è ≥ x. Se non ce n’è nessuno, x è maggiore di tutti i valori finali e prolunga la sottosequenza più lunga, quindi aggiungilo. Altrimenti, sostituisci quel valore finale con x: la sottosequenza più corta di un elemento termina con un valore minore di x, quindi aggiungere x dà la stessa lunghezza con un valore finale più piccolo.

Per [3, 1, 8, 2, 5, 9, 4, 7], tails diventa [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7], e la sua lunghezza, 4, è la risposta. Nel passaggio [1, 2, 4, 9], il 4 viene dopo il 9 nell’input, quindi tails non è di per sé una sottosequenza; solo la sua lunghezza ha un significato. Il metodo è chiamato anche ordinamento per pazienza, dal nome del gioco di carte in cui ogni valore finale è la carta in cima a una pila.

Ogni elemento richiede una ricerca binaria su al massimo n valori finali: circa 2500 × 12 = 30.000 passaggi per l’input più grande.

Algoritmo

Inizia con un elenco vuoto tails.
Per ogni x in nums, esegui una ricerca binaria del primo indice k tale che tails[k] ≥ x.
Se nessuna coda è ≥ x, aggiungi x.
Altrimenti imposta tails[k] = x.
Restituisci la lunghezza di tails.

from bisect import bisect_left


def lengthOfLIS(nums):
    # tails[k]: the smallest last value of any increasing subsequence of length k + 1
    tails = []
    for x in nums:
        k = bisect_left(tails, x)  # the first tail that is >= x
        if k == len(tails):
            tails.append(x)  # x extends the longest subsequence so far
        else:
            tails[k] = x  # x is a smaller ending for length k + 1
    return len(tails)

Trappole e casi limite

La maggior parte delle risposte sbagliate deriva dal confondere cosa contiene la tabella o dal considerare i valori uguali come crescenti.

Restituire ending[n-1] invece della voce più grande. In [1, 2, 3, 0] l’ultima voce è 1, ma la risposta è 3.
Confrontare con ≤ invece di <. [7, 7, 7, 7] deve restituire 1, non 4.
Nella versione con tails, cercare la prima coda > x invece di ≥ x. Con i duplicati, questo aggiunge il secondo 7 dopo il primo e conta i valori uguali come una sottosequenza più lunga.
Considerare tails come la sottosequenza stessa. I suoi valori possono provenire da sottosequenze diverse, quindi stampala solo se tieni traccia separatamente dei predecessori.
Risolvere per errore la versione contigua. In [3, 1, 8, 2, 5, 9, 4, 7] la sequenza crescente più lunga di elementi adiacenti è 2, 5, 9 (lunghezza 3), mentre la risposta è 4.
In Lua e R, gli array iniziano da 1, quindi un indicatore prev = -1 basato su indici da 0 diventa 0 e la ricerca binaria viene eseguita sugli indici da 1 alla dimensione corrente.

Domande frequenti4

Qual è la complessità temporale della sottosequenza crescente più lunga?

Il metodo tails richiede un tempo di O(n log n) e uno spazio di O(n): una ricerca binaria per elemento. La tabella di programmazione dinamica su ogni coppia di indici richiede un tempo di O(n²), mentre provare ogni sottosequenza richiede O(2ⁿ). Per n = 2500, si tratta di circa 30.000, 3 milioni e un numero astronomico di passaggi.

Perché il metodo di ordinamento per pazienza restituisce la lunghezza corretta?

Dopo ogni elemento, tails[k] contiene il valore più piccolo con cui può terminare qualsiasi sottosequenza crescente di lunghezza k+1 vista finora. L'aggiunta avviene solo quando x è maggiore di ogni valore finale, il che significa che ora esiste una sottosequenza più lunga di una unità rispetto a qualsiasi sottosequenza precedente. La sostituzione non cambia mai la lunghezza, abbassa solo un valore finale, quindi la lunghezza della lista è sempre la lunghezza della sottosequenza crescente più lunga.

Come si ottiene la sottosequenza crescente più lunga effettiva, non solo la sua lunghezza?

Registra un genitore per ogni elemento. Nella tabella O(n²), il genitore di i è il j che ha assegnato il suo valore a ending[i]. Nel metodo tails, memorizza l'indice dell'elemento dietro ogni coda e, quando un elemento viene inserito, imposta il suo genitore sull'indice memorizzato una posizione alla sua sinistra. Poi risali i genitori partendo dalla fine della sottosequenza più lunga e inverti il risultato.

Come si trova invece la sottosequenza non decrescente più lunga?

Consenti valori adiacenti uguali. Nella tabella, usa nums[j] ≤ nums[i]. Nel metodo delle code, cerca la prima coda strettamente maggiore di x invece che maggiore o uguale, così un valore uguale estende la lista anziché sostituire una coda. [7, 7, 7, 7] restituisce quindi 4.

Python

def lengthOfLIS(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [3, 1, 8, 2, 5, 9, 4, 7]

Atteso

Longest Increasing Subsequence

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prendi o salta ogni elemento

Sottosequenza più lunga che termina a ciascun indice

Coda più corte con la ricerca binaria

Trappole e casi limite

Domande frequenti4

Problemi simili