Se dă un tablou cu $n$ numere: $a$.Sarcina este de a găsi cea mai lungă subsecvență, strict crescătoare, din $a$.

În mod formal, căutăm cea mai lungă secvență de indici $i_1, \dots i_k$ astfel încât$$i_1 < i_2 < \dots < i_k,\\a < a < \dots < a$$

În acest articol vom discuta mai mulți algoritmi pentru rezolvarea acestei sarcini.De asemenea, vom discuta și alte probleme care pot fi reduse la această problemă.

Soluție în $O(n^2)$ cu programare dinamică

Programarea dinamică este o tehnică foarte generală care permite rezolvarea unei clase uriașe de probleme.aici aplicăm tehnica pentru sarcina noastră specifică.

Prima dată vom căuta doar lungimea celei mai lungi subsecvențe crescătoare, și abia mai târziu vom învăța cum să restabilim subsecvența însăși.

Căutarea lungimii

Pentru a îndeplini această sarcină, definim un array $d$, unde $d$ este lungimea celei mai lungi subsecvențe crescătoare care se termină în elementul cu indicele $i$.Vom calcula acest tablou treptat: mai întâi $d$, apoi $d$, și așa mai departe. după ce acest tablou este calculat, răspunsul la problemă va fi valoarea maximă din tabloul $d$.

Să fie deci indicele curent $i$.Adică dorim să calculăm valoarea $d$ și toate valorile anterioare $d, \dots, d$ sunt deja cunoscute. în acest caz există două opțiuni:

• $d = 1$: subsecvența cerută este formată numai din elementul $a$.
• $d > 1$: atunci în subsecvența cerută se află un alt număr înainte de numărul $a$. să ne concentrăm asupra acelui număr:poate fi orice element $a$ cu $j = 0 \dots i-1$ și $a < a$.În acest fel putem calcula $d$ folosind următoarea formulă:Dacă fixăm indicele $j$, atunci cea mai lungă subsecvență crescătoare care se termină în cele două elemente $a$ și $a$ are lungimea $d + 1$.Toate aceste valori $d$ sunt deja cunoscute, deci putem calcula direct $d$ cu:$$d = \max_{\substack{j = 0 \dots i-1 \\\\ a < a}}. \left(d + 1\right)$$$

Dacă combinăm aceste două cazuri, obținem răspunsul final pentru $d$:

$$d = \max\left(1, \max_{\substack{j = 0 \dots i-1 \\\ a < a}}. \left(d + 1\right)\right)$$

Implementare

Iată o implementare a algoritmului descris mai sus, care calculează lungimea celei mai lungi subsecvențe crescânde.

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;}

Restabilirea subsecvenței

Până acum am învățat doar cum să găsim lungimea subsecvenței, dar nu și cum să găsim subsecvența în sine.

Pentru a putea restabili subsecvența generăm un tablou auxiliar suplimentar $p$ pe care îl vom calcula alături de tabloul $d$. $p$ va fi indicele $j$ al penultimului element din cea mai lungă subsecvență crescătoare care se termină în $i$. cu alte cuvinte, indicele $p$ este același indice $j$ la care a fost obținută cea mai mare valoare $d$.Această matrice auxiliară $p$ indică într-un fel strămoșii.

Apoi, pentru a deduce subsecvența, nu trebuie decât să începem de la indicele $i$ cu valoarea maximă $d$ și să urmărim strămoșii până când am dedus întreaga subsecvență, adică până când ajungem la elementul cu $d = 1$.

Implementarea restaurării

Vom modifica puțin codul din secțiunile anterioare.Vom calcula matricea $p$ alături de $d$, iar apoi vom calcula subsecvența.

Pentru comoditate, inițial vom atribui strămoșii cu $p = -1$. pentru elementele cu $d = 1$, valoarea strămoșilor va rămâne $-1$, ceea ce va fi puțin mai convenabil pentru refacerea subsecvenței.

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;}

Modalitate alternativă de restabilire a subsecvenței

Este de asemenea posibil să restabilim subsecvența fără matricea auxiliară $p$.Putem recalcula pur și simplu valoarea curentă a lui $d$ și, de asemenea, să vedem cum a fost atins maximul.

Această metodă duce la un cod puțin mai lung, dar în schimb economisim ceva memorie.

Soluție în $O(n \log n)$ cu programare dinamică și căutare binară

Pentru a obține o soluție mai rapidă pentru problemă, construim o soluție diferită de programare dinamică care rulează în $O(n^2)$, iar ulterior o îmbunătățim la $O(n \log n)$.

Vom folosi matricea de programare dinamică $d$.De data aceasta $d$ va fi elementul la care se termină o subsecvență de lungime $i$. dacă există mai multe astfel de secvențe, atunci o luăm pe cea care se termină în cel mai mic element.

Ințial presupunem că $d = -\infty$ și pentru toate celelalte elemente $d = \infty$.

Vom prelucra din nou treptat numerele, mai întâi $a$, apoi $a$, etc., iar la fiecare pas menținem tabloul $d$ astfel încât acesta să fie la zi.

După prelucrarea tuturor elementelor lui $a$ lungimea subsecvenței dorite este cea mai mare $l$ cu $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;}

Acum facem două observații importante.

Tabloul $d$ va fi întotdeauna ordonat: $d \le d$ pentru toate $i = 1 \puncte n$. și, de asemenea, elementul $a$ nu va actualiza decât cel mult o singură valoare $d$.

Din acest motiv putem găsi acest element în tabloul $d$ folosind căutarea binară în $O(\log n)$.De fapt, căutăm pur și simplu în matricea $d$ primul număr care este strict mai mare decât $a$ și încercăm să actualizăm acest element în același mod ca în implementarea de mai sus.

Implementare

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;}

Restabilirea subsecvenței

Este de asemenea posibilă restabilirea subsecvenței folosind această abordare.De data aceasta trebuie să menținem două tablouri auxiliare. unul care ne spune indicele elementelor din $d$. și din nou trebuie să creăm un tablou de „strămoși” $p$. $p$ va fi indicele elementului anterior pentru subsecvența optimă care se termină în elementul $i$.

Este ușor să menținem aceste două tablouri în cursul iterației asupra tabloului $a$ în paralel cu calculele lui $d$.Iar la sfârșit nu este dificil să se restabilească subsecvența dorită folosind aceste array-uri.

Soluție în $O(n \log n)$ cu structuri de date

În loc de metoda de mai sus pentru calcularea celei mai lungi subsecvențe crescătoare în $O(n \log n)$ putem rezolva problema și în alt mod: folosind câteva structuri de date simple.

Să ne întoarcem la prima metodă. amintiți-vă că $d$ este valoarea $d + 1$ cu $j < i$ și $a < a$.

Atunci, dacă definim un array suplimentar $t$ astfel încât $$t] = d,$$ atunci problema calculării valorii $d$ este echivalentă cu găsirea valorii maxime într-un prefix al array-ului $t$:$$d = \max\left(t – 1] + 1\right)$$

Problema găsirii maximului unui prefix al unui array (care se schimbă) este o problemă standard care poate fi rezolvată de multe structuri de date diferite. De exemplu, putem folosi un arbore de segmente sau un arbore Fenwick.

Această metodă are în mod evident unele neajunsuri:din punct de vedere al lungimii și al complexității implementării, această abordare va fi mai proastă decât metoda care folosește căutarea binară. în plus, dacă numerele de intrare $a$ sunt deosebit de mari, atunci va trebui să folosim unele trucuri, cum ar fi comprimarea numerelor (adică renumerotarea lor de la $0$ la $n-1$), sau să folosim un arbore de segmente implicit (generăm doar ramurile arborelui care sunt importante).În caz contrar, consumul de memorie va fi prea mare.

Pe de altă parte, această metodă are și unele avantaje:cu această metodă nu trebuie să vă gândiți la nicio proprietate complicată în soluția de programare dinamică. și această abordare ne permite să generalizăm problema foarte ușor (vezi mai jos).

Probleme înrudite

Iată câteva probleme care sunt strâns legate de problema găsirii celei mai lungi subsecvențe crescătoare.

Cea mai lungă subsecvență nedecrescătoare

Aceasta este de fapt aproape aceeași problemă. numai că acum este permisă folosirea de numere identice în subsecvență.

Soluția este în esență tot aproape aceeași.Trebuie doar să schimbăm semnele de inegalitate și să facem o ușoară modificare a căutării binare.

Numărul celor mai lungi subsecvențe crescânde

Potem folosi prima metodă discutată, fie varianta $O(n^2)$, fie varianta care folosește structuri de date.Trebuie doar să stocăm suplimentar în câte moduri putem obține cele mai lungi subsecvențe crescătoare care se termină în valorile $d$.

Numărul de moduri de a forma o subsecvență crescătoare cea mai lungă care se termină în $a$ este suma tuturor modurilor pentru toate subsecvențele crescătoare cele mai lungi care se termină în $j$ unde $d$ este maxim.Pot exista mai multe astfel de $j$, așa că trebuie să le însumăm pe toate.

Utilizând un arbore de segmente, această abordare poate fi, de asemenea, implementată în $O(n \log n)$.

Nu este posibil să se utilizeze abordarea de căutare binară pentru această sarcină.

Cel mai mic număr de subsecvențe non-increscătoare care acoperă o secvență

Pentru un array dat cu $n$ numere $a$ trebuie să colorăm numerele în cel mai mic număr de culori, astfel încât fiecare culoare să formeze o subsecvență non-increscătoare.

Pentru a rezolva această problemă, observăm că numărul minim de culori necesare este egal cu lungimea celei mai lungi subsecvențe crescătoare.

Probă: Trebuie să demonstrăm dualitatea acestor două probleme.

Să notăm prin $x$ lungimea celei mai lungi subsecvențe crescătoare și prin $y$ cel mai mic număr de subsecvențe ne-crescătoare care formează o acoperire. trebuie să demonstrăm că $x = y$.

Este clar că $y < x$ nu este posibil, deoarece dacă avem $x$ elemente strict crescătoare, atunci nici două nu pot face parte din aceeași subsecvență ne-crescătoare.Prin urmare, avem $y \ge x$.

Acum arătăm că $y > x$ nu este posibil prin contradicție. să presupunem că $y > x$. atunci considerăm orice set optim de subsecvențe ne-crescătoare $y$.Transformăm acest ansamblu în set în felul următor: atâta timp cât există două astfel de subsecvențe astfel încât prima să înceapă înaintea celei de-a doua subsecvențe, iar prima secvență să înceapă cu un număr mai mare sau egal cu cea de-a doua, atunci dezlegăm acest număr de început și îl atașăm la începutul celei de-a doua.După un număr finit de pași avem $y$ subsecvențe, iar numerele lor de început vor forma o subsecvență crescătoare de lungime $y$. întrucât am presupus că $y > x$ am ajuns la o contradicție.

Deci rezultă că $y = x$.

Restabilirea secvențelor: Împărțirea dorită a secvenței în subsecvențe se poate face cu lăcomie. adică se merge de la stânga la dreapta și se atribuie numărul curent sau acea subsecvență care se termină cu numărul minim care este mai mare sau egal cu cel curent.

Probleme practice

• Topcoder – IntegerSequence
• Topcoder – AutoMarket
• Codeforces – Tourist
• Codeforces – Tourist
• Codeforces – LCIS
• SPOJ – SUPRAVIEȚUIRE
• Topcoder – BridgeArrangement
• ACMSGURU – „Nord-Est”

.