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 su ogni coppia di indici richiede un tempo di O(n²) , mentre provare ogni sottosequenza richiede O(2ⁿ) .

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

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

MedioProgrammazione dinamica Ricerca binaria

+10

Ti viene fornito un elenco di numeri interi nums. Una sottosequenza conserva alcuni elementi, nel loro ordine originale, e scarta gli altri; gli elementi conservati non devono necessariamente essere consecutivi. 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 numeri interi tra 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: 1, 2, 5, 9 cresce, e così anche 1, 2, 5, 7 e 1, 2, 4, 7: lunghezza 4. Nessuna scelta di cinque valori continua a crescere.

Per approfondire

Puoi restituire una delle sottosequenze crescenti più lunghe, insieme alla sua lunghezza, continuando a impiegare un tempo O(n log n)?

Suggerimenti

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

0 di 3 aperti

Soluzione

Una lista di n numeri ha 2^n sottosequenze, troppe per controllarle tutte. Chiedersi, per ogni indice, quanto è lunga la migliore sottosequenza crescente che termina esattamente lì produce una tabella O(n²). La versione più veloce mantiene, per ogni lunghezza, il valore più piccolo con cui può terminare una sottosequenza di quella lunghezza, e inserisce ciascun elemento usando una ricerca binaria.

Prendi o salta ogni elemento

Corretto, ma non termina sui test più grandi

Intuizione

Decidi per ogni elemento se mantenerlo; puoi mantenere nums[i] solo quando è maggiore dell'ultimo valore mantenuto. longest(i, prev) è il numero massimo di elementi che puoi ancora aggiungere a partire dall'indice i, quando l'ultimo elemento mantenuto si trova in prev (o -1). Saltare dà longest(i+1, prev); mantenere dà 1 + longest(i+1, i). Ogni sottosequenza crescente è un percorso composto da queste scelte.

Con 1, 2, 3, ..., n entrambi i rami restano aperti e le chiamate raddoppiano a ogni elemento: 2^40 è già circa 10^12. Eppure esistono al massimo n² coppie diverse (i, prev).

Algoritmo

Scrivi longest(i, prev), dove prev è l’indice dell’ultimo elemento mantenuto, oppure -1.
Se i supera 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)

La sottosequenza più lunga che termina in ciascun indice

Intuizione

Sia ending[i] la lunghezza della sottosequenza crescente più lunga il cui ultimo elemento è nums[i]. L'elemento precedente a nums[i], se esiste, è un nums[j] tale che j < i e nums[j] < nums[i], e la parte fino a esso dovrebbe essere il più lunga possibile. Quindi ending[i] = 1 + max(ending[j]) per tali j, oppure 1 se non ce n'è nessuno. Compilala da sinistra a destra.

Per [3, 1, 8, 2, 5, 9, 4, 7] la tabella è [1, 1, 2, 2, 3, 4, 3, 4]: 5 può seguire 3, 1 o 2, e il migliore tra questi ha lunghezza 2, quindi ending[4] = 3. La risposta è il valore più grande, poiché la sottosequenza migliore può terminare in qualsiasi posizione.

n(n-1)/2 confronti: circa 3.1 × 10^6 per n = 2500.

Algoritmo

Crea ending con ogni voce impostata 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 è 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)

Code più piccoli con ricerca binaria

Intuizione

Per ogni lunghezza, conserva solo il valore più piccolo con cui può terminare una sottosequenza crescente di quella lunghezza: tails[k] per la lunghezza k+1. Un valore finale più piccolo non è mai peggiore: tutto ciò che può seguire un 9 può seguire anche un 5. tails rimane strettamente crescente: elimina l'ultimo valore di una sottosequenza crescente di lunghezza k+2 e ottieni una sottosequenza di lunghezza k+1 che termina con un valore minore.

Per ogni x, cerca con la ricerca binaria la prima coda ≥ x. Se non ce n'è nessuna, aggiungi x: estende la sottosequenza più lunga. Altrimenti, sostituisci quella coda con x: la sottosequenza più corta di una unità termina con un valore minore di x, quindi x dà la stessa lunghezza con un valore finale più piccolo.

Per l'esempio 1, tails diventa [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7]: lunghezza 4. In [1, 2, 4, 9], il 4 viene dopo il 9, quindi solo la lunghezza di tails ha significato.

Algoritmo

Inizia con una lista vuota tails.
Per ogni x in nums, cerca con la ricerca binaria il 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

Restituire ending[n-1] invece dell'elemento più grande. Per [1, 2, 3, 0] l'ultimo elemento è 1, ma la risposta è 3.
Confrontare con ≤ invece che con <. [7, 7, 7, 7] deve restituire 1, non 4.
Nella versione con tails, cercare la prima coda > x invece di ≥ x. Il secondo 7 viene quindi aggiunto dopo il primo, contando i valori uguali come crescenti.
Risolvere per errore la versione contigua. Nell'esempio 1 la sequenza crescente più lunga di elementi adiacenti è 2, 5, 9 (lunghezza 3), mentre la risposta è 4.
Mantenere gli indici a base 0 in Lua o R, dove gli array iniziano da 1. Il marcatore prev = -1 diventa 0 e la ricerca binaria viene eseguita sugli indici da 1 alla dimensione corrente.

Domande frequenti3

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 su ogni coppia di indici richiede un tempo di O(n²), mentre provare ogni sottosequenza richiede O(2ⁿ).

Che cos'è il patience sorting nella sottosequenza crescente più lunga?

È il metodo delle code, chiamato così per via di un gioco di carte. Ogni coda è la carta in cima a una pila: una carta va sulla pila più a sinistra la cui carta in cima ha un valore almeno pari al suo, oppure avvia una nuova pila. Il numero di pile è la risposta.

Come trovi invece la sottosequenza non decrescente più lunga?

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

def lengthOfLIS(nums):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso

Longest Increasing Subsequence

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prendi o salta ogni elemento

La sottosequenza più lunga che termina in ciascun indice

Code più piccoli con ricerca binaria

Trappole e casi limite

Domande frequenti3

Problemi simili