Subșir crescător de lungime maximă


Etichete: nicio etichetă
#sclm : Se dă un șir cu n elemente, numere naturale. Determinați un cel mai lung subșir crescător al șirului.

De exemplu, pentru n=10 și șirul A=(5, 10, 7, 4, 5, 8, 9, 8, 10, 2), cel mai lung subșir crescător va conține 5 elemente (5, 7, 8, 9, 10) sau (4, 5, 8, 9, 10).

Problema este una clasică și se rezolvă prin programare dinamică. Subșirul cerut se mai numește și subșir crescător maximal.

O soluție O(n^2)

Determinarea lungimii maxime

Pentru a determina lungimea maximă a unui subșir crescător al lui A, vom construi un șir suplimentar LG[], cu proprietatea că LG[i] este lungimea maximă a unui subșir care se începe în A[i]. Atunci lungimea maximă a unui subșir crescător va fi cel mai mare element din tabloul LG.

Vom construi șirul LG progresiv, începând de la ultimul element din A, bazându-ne pe următoarele observații:

  • LG[i] ≥ 1, ∀i
  • LG[n] = 1
  • vom determina LG[i] astfel: analizăm toate elementele A[j], cu j>i și îl alegem pe acela pentru care LG[j] este maxim și A[i]≤A[j]. Fie jmax indicele acestui element. Atunci LG[i] devine LG[i] = LG[jmax] + 1 – elementul A[i] se lipește de subșirul care începe în A[jmax].

Secvență C++:

LG[n] = 1;
for(int i = n - 1 ; i > 0 ; i --)
{
    LG[i] = 1;
    for(int j = i + 1 ; j <= n; ++ j)
        if(A[i] <= A[j] && LG[i] < LG[j] + 1)
            LG[i] = LG[j] + 1;
}

După construirea șirului LG, lungimea subșirului maximal se determină ca fiind cea mai mare valoare din tabloul LG.

int pmax = 1;
for(int i = 2 ; i <= n ; i ++)
    if(LG[i] > LG[pmax])
        pmax = p;
cout << LG[pmax];

Reconstituirea subșirului

Există mai multe modalități de reconstituire a subșirului maximal. De asemenea, trebuie spus că pot exista mai multe șiruri maximale; în unele probleme poate fi determinat oricare, în altele trebuie determinat un subșir cu proprietăți suplimentare.

O soluție constă în construirea unui șir suplimentar, Next cu următoarea semnificație: Next[i] este următorul element în subșirul crescător maximal care începe cu A[i]. Dacă nu există un element următor, atunci LG[i] = -1. Acest tabloul se construiește în același timp cu LG, astfel:

LG[n] = 1, Next[n] = -1;
for(int i = n - 1 ; i > 0 ; i --)
{
    LG[i] = 1 , Next[n] = -1;
    for(int j = i + 1 ; j <= n; ++ j)
        if(A[i] <= A[j] && LG[i] < LG[j] + 1)
            LG[i] = LG[j] + 1, Next[i] = j;
}

Pentru a afișa subșirul, vom extrage informațiile necesare din șirul Next, pornind de la indicele pmax determinat mai sus:

int p = pmax;
do
{
    cout << p << " ";
    p = Next[p];
}
while(p != -1);

Putem reconstitui subșirul fără a construi șirul Next. La fiecare pas al structurii repetitive de mai sus vom determina un indice pUrm cu proprietatea că LG[pUrm]==LG[p]-1 și A[p] ≤ A[pUrm]:

int p = pmax;
do
{
    cout << p << " ";
    int pUrm = p + 1;
    while(pUrm <= n && ! (A[pUrm] >= A[p] && LG[pUrm] == LG[p] - 1))
        pUrm ++;
    if(pUrm <= n)
        p = pUrm;
    else
        p = -1;
}
while(p != -1);

Altă soluție O(n^2)

Putem regândi algoritmul de mai sus, astfel încât LG[i] să reprezinte lungime a maximă a unui subșir maximal care se termină în A[i].

  • evident, LG[1]=1;
  • pentru fiecare element A[i] din șirul dat, vom parcurge elementele din fața sa și îl vom alege pe A[p] atfel încât A[p]≤A[i] și LG[p] este maxim. În acest caz, A[i] se adaugă la subșirul care se încheie în A[p], adică LG[i] devine LG[p]+1.

Lungimea subșriului maximal este cea mai mare valoare din LG, iar recosntituirea lui se face asemănător cu metoda de mai sus, folosind un șir de predecesori Prev[], unde Prev[i] este elementul din fața lui A[i] în subșirul crescător maximal care se încheie în A[i].

O soluție O(n•log n)

Algoritmul de mai sus are complexitate pătratică. Următoarea idee permite obținerea unui algoritm \(O(n \cdot \log{n})\).

Vom construi șirul D[], unde D[j] reprezintă un element al șirului A în care se termină un subșir crescător maximal de lungime j. Numărul de elemente pe care le va avea la final tabloul D va reprezenta lungimea subșirului crescător maximal al întregului șir A.

Vom construi șirul D în felul următor:

  • fie k lungimea șirului D. Inițializăm k=1 și D[k]=A[1];
  • parcurgem șirul A, începând de la al doilea element:
    • dacă A[i]≥D[k], îl adăugăm pe A[i] în șirul D – subșirul crescător maximal al lui A crește cu încă un element
    • dacă A[i]<D[k], vom înlocui cu A[i] pe cel mai mai mic element din D care este mai mare decât acesta

Exemplu

Pentru A=(5, 10, 7, 4, 5, 8, 9, 8, 10, 2).

Inițial k=1; D[k]=5; parcurgem șirul A, începând de la al doilea element:

i A[i] Condiție Acțiune D[]
2 10 A[i]>=D[k] adăugare (5, 10)
3 7 A[i]<D[k] înlocuire (5, 7)
4 4 A[i]<D[k] înlocuire (4, 7)
5 5 A[i]<D[k] înlocuire (4, 5)
6 8 A[i]>=D[k] adăugare (4, 5, 8)
7 9 A[i]>=D[k] adăugare (4, 5, 8, 9)
8 8 A[i]<D[k] înlocuire (4, 5, 8, 8)
9 10 A[i]>=D[k] adăugare (4, 5, 8, 8, 10)
10 2 A[i]<D[k] înlocuire (2, 5, 8, 8, 10)

Observații

  • valorile din șirul D sunt în ordine crescătoare
  • fiecare element din șirul A modifică exact un element din șirul D (prin adăugare sau înlocuire).

Aceste observații ne permit să folosim căutarea binară pentru a stabili elementul din D care va fi înlocuit la fiecare pas: vom căuta primul element din D care este mai mare decât A[i]. Acest lucru poate fi realizat manual sau folosind funcția STL upper_bound. Complexitatea va fi \(O(n \cdot \log k)\).

Secvență C++

k = 1, D[k] = A[1];
for(int i = 2 ; i <= n ; i ++)
{
    if(A[i] >= D[k])
        P[++k] = A[i];
    else
    {
        int st = 1 , dr = k , poz = k + 1;
        while(st <= dr)
        {
            int m = (st + dr) / 2;
            if(D[m] > A[i])
                poz = m , dr = m - 1;
            else
                st = m + 1;
        }
        D[poz] = A[i];
    }
}
cout << k << endl;

Reconstituirea subșirului

Pentru a reconstitui sub șirul crescător maximal vom folos încă un șir P[], unde P[i] reprezintă poziția în șirul D unde a fost plasat (prin adăugare sau prin înlocuire) A[i].

Probleme propuse