Ci viene dato un array con $n$ numeri: $a$. Il compito è trovare la più lunga sottosequenza strettamente crescente in $a$.

Formalmente cerchiamo la più lunga sequenza di indici $i_1, \punti i_k$ tale che$$i_1 < i_2 < \punti < i_k,\a < a < \punti < a$$

In questo articolo discutiamo diversi algoritmi per risolvere questo compito e alcuni altri problemi che possono essere ridotti a questo problema.

Soluzione in $O(n^2)$ con programmazione dinamica

La programmazione dinamica è una tecnica molto generale che permette di risolvere un’enorme classe di problemi.

Prima cercheremo solo la lunghezza della sottosequenza crescente più lunga, e solo dopo impareremo come ripristinare la sottosequenza stessa.

Trovare la lunghezza

Per realizzare questo compito, definiamo un array $d$, dove $d$ è la lunghezza della sottosequenza crescente più lunga che finisce nell’elemento all’indice $i$.Calcoleremo questo array gradualmente: prima $d$, poi $d$, e così via.Dopo che questo array è stato calcolato, la risposta al problema sarà il valore massimo nell’array $d$.

Perciò lasciamo che l’indice corrente sia $i$.Cioè vogliamo calcolare il valore $d$ e tutti i valori precedenti $d, \punti, d$ sono già noti.Allora ci sono due opzioni:

• $d = 1$: la sottosequenza richiesta consiste solo nell’elemento $a$.
• $d > 1$: allora nella sottosequenza richiesta c’è un altro numero prima del numero $a$.Concentriamoci su questo numero: può essere un qualsiasi elemento $a$ con $j = 0 \punti i-1$ e $a < a$.In questo modo possiamo calcolare $d$ usando la seguente formula:Se fissiamo l’indice $j$, allora la più lunga sottosequenza crescente che termina con i due elementi $a$ e $a$ ha la lunghezza $d + 1$.Tutti questi valori $d$ sono già noti, quindi possiamo calcolare direttamente $d$ con:$$d = \max_{\sottostack{j = 0 \punti i-1 \a < a}} \sinistra(d + 1\destra)$$

Se combiniamo questi due casi otteniamo la risposta finale per $d$:

$$d = \max_{substack{j = 0 \punti i-1 \ a < a}} \sinistra(d + 1\destra)\destra)$$

Implementazione

Ecco un’implementazione dell’algoritmo descritto sopra, che calcola la lunghezza della sottosequenza crescente più lunga.

int lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a) d = max(d, d + 1); } } int ans = d; for (int i = 1; i < n; i++) { ans = max(ans, d); } return ans;}

Ripristino della sottosequenza

Finora abbiamo solo imparato come trovare la lunghezza della sottosequenza, ma non come trovare la sottosequenza stessa.

Per poter ripristinare la sottosequenza generiamo un ulteriore array ausiliario $p$ che calcoleremo insieme all’array $d$.$p$ sarà l’indice $j$ del penultimo elemento della sottosequenza crescente più lunga che termina in $i$.In altre parole l’indice $p$ è lo stesso indice $j$ in cui è stato ottenuto il valore più alto $d$.Questa matrice ausiliaria $p$ punta in un certo senso agli antenati.

Poi per derivare la sottosequenza, basta iniziare dall’indice $i$ con il massimo $d$, e seguire gli antenati fino a quando abbiamo dedotto l’intera sottosequenza, cioè fino a quando non raggiungiamo l’elemento con $d = 1$.

Implementazione del ripristino

Cambieremo un po’ il codice delle sezioni precedenti.Calcoleremo l’array $p$ accanto a $d$, e poi calcoleremo la sottosequenza.

Per comodità assegneremo originariamente gli antenati con $p = -1$.Per gli elementi con $d = 1$, il valore degli antenati rimarrà $-1$, che sarà leggermente più conveniente per il ripristino della sottosequenza.

vector<int> lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1), p(n, -1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a && d < d + 1) { d = d + 1; p = j; } } } int ans = d, pos = 0; for (int i = 1; i < n; i++) { if (d > ans) { ans = d; pos = i; } } vector<int> subseq; while (pos != -1) { subseq.push_back(a); pos = p; } reverse(subseq.begin(), subseq.end()); return subseq;}

Modo alternativo di ripristinare la sottosequenza

È anche possibile ripristinare la sottosequenza senza l’array ausiliario $p$.Possiamo semplicemente ricalcolare il valore attuale di $d$ e vedere anche come è stato raggiunto il massimo.

Questo metodo porta ad un codice leggermente più lungo, ma in cambio risparmiamo un po’ di memoria.

Soluzione in $O(n \log n)$ con programmazione dinamica e ricerca binaria

Al fine di ottenere una soluzione più veloce per il problema, costruiamo un’altra soluzione di programmazione dinamica che gira in $O(n^2)$, e poi successivamente la miglioriamo a $O(n \log n)$.

Utilizzeremo l’array di programmazione dinamica $d$.Questa volta $d$ sarà l’elemento in cui termina una sottosequenza di lunghezza $i$.Se ci sono più sequenze di questo tipo, allora prendiamo quella che termina nell’elemento più piccolo.

Inizialmente assumiamo $d = -\infty$ e per tutti gli altri elementi $d = \infty$.

Eseguiremo di nuovo gradualmente i numeri, prima $a$, poi $a$, ecc, e in ogni passo manterremo l’array $d$ in modo che sia aggiornato.

Dopo aver processato tutti gli elementi di $a$ la lunghezza della sottosequenza desiderata è la più grande $l$ con $d < \infty$.

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { for (int j = 1; j <= n; j++) { if (d < a && a < d) d = a; } } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

Facciamo ora due importanti osservazioni.

L’array $d$ sarà sempre ordinato: $d \le d$ per tutti $i = 1 \punti n$.E anche l’elemento $a$ aggiornerà al massimo un valore $d$.

Quindi possiamo trovare questo elemento nell’array $d$ usando la ricerca binaria in $O(\log n)$.Infatti stiamo semplicemente cercando nell’array $d$ il primo numero che è strettamente maggiore di $a$, e cerchiamo di aggiornare questo elemento nello stesso modo dell’implementazione precedente.

Implementazione

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { int j = upper_bound(d.begin(), d.end(), a) - d.begin(); if (d < a && a < d) d = a; } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

Ripristino della sottosequenza

È anche possibile ripristinare la sottosequenza usando questo approccio.Questa volta dobbiamo mantenere due array ausiliari: uno che ci dice l’indice degli elementi in $d$ e l’altro che crea un array di “antenati” $p$. $p$ sarà l’indice dell’elemento precedente per la sottosequenza ottimale che termina nell’elemento $i$.

È facile mantenere questi due array nel corso dell’iterazione sull’array $a$ accanto ai calcoli di $d$.E alla fine non è difficile ripristinare la sottosequenza desiderata usando questi array.

Soluzione in $O(n \log n)$ con strutture dati

Invece del metodo sopra descritto per calcolare la sottosequenza crescente più lunga in $O(n \log n)$ possiamo anche risolvere il problema in un modo diverso: usando alcune semplici strutture dati.

Torniamo al primo metodo: ricordate che $d$ è il valore $d + 1$ con $j < i$ e $a < a$.

Quindi se definiamo un ulteriore array $t$ tale che $t] = d,$ allora il problema di calcolare il valore $d$ è equivalente a trovare il valore massimo in un prefisso dell’array $t$:$$d = \max\left(t – 1] + 1\right)$$

Il problema di trovare il massimo di un prefisso di un array (che cambia) è un problema standard che può essere risolto da molte strutture dati diverse. Per esempio possiamo usare un albero di Segmento o un albero di Fenwick.

Questo metodo ha ovviamente alcuni difetti: in termini di lunghezza e complessità dell’implementazione questo approccio sarà peggiore del metodo che usa la ricerca binaria.Inoltre se i numeri di input $a$ sono particolarmente grandi, allora dovremmo usare alcuni trucchi, come comprimere i numeri (cioè rinumerarli da $0$ a $n-1$), o usare un albero di Segmento implicito (generare solo i rami dell’albero che sono importanti).Altrimenti il consumo di memoria sarà troppo alto.

D’altra parte questo metodo ha anche alcuni vantaggi:con questo metodo non si deve pensare a nessuna proprietà complicata nella soluzione di programmazione dinamica.E questo approccio ci permette di generalizzare il problema molto facilmente (vedi sotto).

Tempi correlati

Ecco diversi problemi che sono strettamente correlati al problema di trovare la più lunga sottosequenza crescente.

La più lunga sottosequenza non decrescente

Questo è in effetti quasi lo stesso problema, solo che ora è permesso usare numeri identici nella sottosequenza.

La soluzione è essenzialmente anche quasi la stessa.Dobbiamo solo cambiare i segni di disuguaglianza, e fare una leggera modifica alla ricerca binaria.

Numero di sottosequenze crescenti più lunghe

Possiamo usare il primo metodo discusso, sia la versione $O(n^2)$ che la versione che usa strutture di dati.Dobbiamo solo memorizzare in quanti modi possiamo ottenere le sottosequenze crescenti più lunghe che terminano nei valori $d$.

Il numero di modi per formare una sottosequenza crescente più lunga che termina in $a$ è la somma di tutti i modi per tutte le sottosequenze crescenti più lunghe che terminano in $j$ dove $d$ è massimo.Ci possono essere più di un $j$, quindi dobbiamo sommarli tutti.

Utilizzando un albero di segmento questo approccio può anche essere implementato in $O(n \log n)$.

Non è possibile utilizzare l’approccio di ricerca binaria per questo compito.

Più piccolo numero di sottosequenze non crescenti che coprono una sequenza

Per un dato array con $n$ numeri $a$ dobbiamo colorare i numeri nel più piccolo numero di colori, in modo che ogni colore formi una sottosequenza non crescente.

Per risolvere questo, notiamo che il numero minimo di colori richiesti è uguale alla lunghezza della sottosequenza crescente più lunga.

Prova:Dobbiamo dimostrare la dualità di questi due problemi.

Denominiamo con $x$ la lunghezza della più lunga sottosequenza crescente e con $y$ il minor numero di sottosequenze non crescenti che formano una copertura.Dobbiamo dimostrare che $x = y$.

È chiaro che $y < x$ non è possibile, perché se abbiamo $x$ elementi strettamente crescenti, allora due non possono essere parte della stessa sottosequenza non crescente.Perciò abbiamo $y \ge x$.

Mostriamo ora che $y > x$ non è possibile per contraddizione.Supponiamo che $y > x$.Allora consideriamo un qualsiasi insieme ottimale di sottosequenze non crescenti di $y$.Trasformiamo questo insieme nel modo seguente: finché ci sono due sottosequenze tali che la prima inizia prima della seconda sottosequenza, e la prima sequenza inizia con un numero maggiore o uguale alla seconda, allora sganciamo questo numero iniziale e lo attacchiamo all’inizio della seconda.Dopo un numero finito di passi abbiamo $y$ sottosequenze, e i loro numeri iniziali formeranno una sottosequenza crescente di lunghezza $y$.Poiché abbiamo assunto che $y > x$ abbiamo raggiunto una contraddizione.

Quindi segue che $y = x$.

Ripristino delle sequenze:La partizione desiderata della sequenza in sottosequenze può essere fatta in modo avido.Cioè andare da sinistra a destra e assegnare il numero corrente o quella sottosequenza che termina con il numero minimo che è maggiore o uguale a quello corrente.

Problemi pratici

• Topcoder – IntegerSequence
• Topcoder – AutoMarket
• Codeforces – Tourist
• Codeforces – LCIS
• SPOJ – SUPPER
• Topcoder – BridgeArrangement
• ACMSGURU – “Nord-Est”