Problema subşirului crescător de lungime maximă

Apărut la iulie 2017 în Algoritmi   |   autor: Dan Pracsiu 0 comentarii

Articol apărut în GInfo ianuarie 2007

Problema determinării subşirului crescător de lungime maximă este una binecunoscută, printre primele care se studiază de obicei la programarea dinamică. Este prezentă în literatura de specialitate sub denumirea de Longest Increasing Substring (LIS).
Ne propunem în acest articol să analizăm această problemă împreună cu alte câteva derivate din aceasta şi care admit rezolvări strîns legate de rezolvarea problemei de bază. În toate problemele care urmează se va face referire la un un şir x = x[1], x[2], ..., x[n] de numere întregi memorat într-un tablou unidimensional de lungime n. Nu vom face precizări suplimentare legate de valoarea lui n şi nici despre intervalul de valori în care se încadrează fiecare element x[i] al şirului. Motivul este că în practică (viaţa reală) nu întotdeauna datele unei probleme sunt bine precizate de la început.

P1. Să se determine lungimea maximă a unui subşir crescător din şirul x.
P2. Să se determine numărul subşirurilor crescătoare de lungime maximă.
P3. Să se determine subşirul crescător de lungime maximă, cel mai mic din punct de vedere lexicografic.
P4. Să se determine lungimea subşirului crescător de lungime minimă.
P5. Să se determine numărul de subşiruri crescătoare din şir
P6. Se dau două şiruri A şi B, ambele de lungime n, cu n par. Se ştie că în ambele şiruri fiecare număr de la 1 la n/2 apare de exact 2 ori. Să se determine lungimea maximă a unui subşir comun al celor două şiruri.

Vom analiza pe rând cele 6 probleme, precizând mai întâi două noţiuni. Un subşir de obţine din şirul iniţial eliminând zero sau mai multe elemente, nu neapărat aflate pe poziţii consecutive. Prin subsecvenţa de forma x[i..j] vom înţelege elementele şirului x aflate pe poziţiile de la i la j în şir, adică x[i], x[i+1], ..., x[j].

P1.
Determinarea lungimii maxime se realizează cu ajutorul unui vector LIS de lungime n, în care LIS[i] este lungimea maximă a unui subşir obţinut din subsecvenţa x[i..n] şi care conţine pe x[i].
Obţinem recurenţele binecunoscute:

Evident, LIS[n]=1. Soluţia va fi max{LIS[i], i = 1..n}
Algoritmul este următorul:

Complexitatea este O(n x n). Există, cum se ştie, algoritmul Robinson-Schensted-Knuth de complexitate O(n log n), pe care nu îl vom analiza aici, un articol legat de acest algoritm a apărut în numărul din octombrie 2006 al Gazetei de Informatică.
Dacă se doreşte şi determinarea nu doar a lungimii maxime, ci şi a unui subşir de lungime maximă, vom avea nevoie de un vector suplimentar Next de lungime n care se construieşte simultan cu LIS şi în care, pentru fiecare i între 1 şi n, în Next[i] se va reţine indicele j unde s-a determinat maximul.

P2.
Se construieşte, pe lângă vectorul LIS, un vector NR de lungime n, în care NR[i] este numărul de subşiruri crescătoare de lungime maximă care se pot construi din secvenţa x[i..n] şi care încep cu x[i]. Evident, NR[n]=1, iar pentru fiecare i de la n-1 la 1, NR[i] va fi egală cu suma acelor valori NR[j] pentru care j>i, LIS[j]=LIS[i]-1 şi x[i]£x[j]. Considerând că s-a obţinut lungimea maximă a unui subşir crescător egală cu Lmax, soluţia va fi dată de suma acelor NR[i] cu LIS[i]=Lmax. Evident, complexitatea algoritmului este tot O(n x n), cu menţiunea că este posibil ca soluţia să fie un număr care nu se poate reprezenta pe 32 de biţi, adică va fi nevoie de operaţii cu numere mari.

P3.
Determinarea subşirului maximal, cel mai mic din punct de vedere lexicografic, poate fi realizată utilizând numai vectorul LIS, construit ca la P1. Ideea de rezolvare este următoarea: considerând Lmax lungimea maximă a unui subşir, se caută poziţia i₁ cu x[i₁] minim şi LIS[i₁]=Lmax. Se caută apoi un indice i₂ > i1 cu x[i₂] minim şi LIS[i₂]=Lmax-1. Procedeul continuă în Lmax paşi, la fiecare pas p (p=1..Lmax) se caută un indice i_p > i_p-1 cu x[i_p] minim şi LIS[i_p]=Lmax–p+1. Soluţia este dată de x[i₁], x[i₂], ..., x[i_Lmax]. Evident, aceste valori sunt ordonate crescător, lucru care se poate demonstra uşor.

P4.
Problema determinării celui mai scurt subşir crescător (SIS – Shortest Increasing Substring) presupune un lucru evident: subşirul minimal nu mai poate fi extins. Adică între oricare două elemente consecutive ale subşirului x_p şi x_q (evident, x_p <= x_q) nu se poate adăuga un element x_k din şirul iniţial cu proprietatea că p < k < q şi x_p <= x_k <= x_q. Spunem că subşirul de lungime minimă este maximal din punctul de vedere al proprietăţii de monotonie. De exemplu, pentru şirul iniţial 3, 1, 7, 2, 9, 5, subşirul crescător maximal de lungime minimă este 3, 5 şi este unic. Subşirul 1, 9 nu este maximal de lungime minimă. El poate fi extins cu valoarea 7, obţinându-se subşirul 1,7, 9 şi are lungimea 3. La fel, subşirul 2, 9 nu este maximal, el poate fi extins prin 1, obţinându-se subşirul 1, 2, 9.
Pentru rezolvare, vom considera vectorul SIS de lungime n, în care SIS[i] va fi lungimea minimă a unui subşir maximal obţinut din subsecvenţa x[i..n] şi care se începe cu x[i]. Recurenţa este una destul de asemănătoare cu cea de la determinarea celui mai lung subşir crescător.

SIS[n] = 1 şi, pentru i = n–1..1, avem:

Condiţia suplimentară care apare în determinarea minimului, anume că nu există k între i+1 şi j-1 cu x[i] <= x[k] <= x[j], este pentru a se evita obţinerea unor subşiruri care nu sunt maximale.
Soluţia va fi valoarea minimă din vectorul SIS. Se poate determina uşor şi subşirul minimal, nu doar lungimea sa, construind vectorul suplimentar NEXT de lungime n, în care NEXT[i] va memora valoarea j pentru care s-a determinat minimul, sau 0 (zero) dacă acest minim nu există, adică atunci când SIS[i] este 1.
Algoritmul, de complexitate pătratică, este descris mai jos.

Pentru cunoscătorii teoriei grafurilor să menţionăm că şirului x i se poate asocia un digraf cu n vârfuri corespunzătoare celor n componente ale şirului iniţial x. Vom construi arce de la un nod i la un nod j dacă i < j, x[i] <= x[j] şi nu există k între i+1..j-1 cu x[i] <= x[k] <= x[j]. Evident digraful obţinut este aciclic. Subşirul maximal de lungime minimă este de fapt un drum de lungime minimă de la un vârf de grad interior 0 la un vârf de grad exterior 0 (unde gradul interior al unui vârf i este numărul de arce care „intră” în i, iar gradul exterior al unui vârf i este numărul de arce care „ies” din i).

P5.
Dacă privim problema din punctul de vedere al teoriei grafurilor, atunci problema cere determinarea numărului de drumuri distincte de la vârfurile de grad interior 0 la nodurile de grad exterior 0 în digraful obţinut asemănător ca la problema precedentă.
Vom prefera o rezolvare care să fie şi pe înţelesul celor care nu au cunoştinţe de grafuri. Construim tabloul unidimensional NR cu n componente, în care NR[i] este numărul de subşiruri crescătoare care există în subsecvenţa x[i..n] şi care încep cu x[i]. Evident, NR[n]=1 şi pentru fiecare i=n-1..1, NR[i] va fi egal cu suma acelor valori NR[j] cu proprietatea că j între i+1..n, x[i] <= x[j] şi nu există k între i+1..j-1 astfel încât x[i] <= x[k] <= x[j]. Observaţi condiţiile care sunt preluate de la determinarea numărului de subşiruri maximale crescătoare şi de la determinarea unui subşir crescător de lungime minimă. Soluţia se obţine sumând acele valori NR[i] cu proprietatea că x[i] < x[j], pentru orice j între 1..i-1. Evident, NR[1] apare mereu în această sumă.

Complexitatea este O(n x n), cu menţiunea că este posibil ca rezultatul să nu poată fi reprezentat pe 32 sau 64 de biţi, în acest caz fiind nevoie de operaţii cu numere mari.

P6.
Este vorba de o particularizare a problemei cunoscută ca Longest Common Subsequence (LCS), în care se cere determinarea celui mai lung subşir comun a două şiruri A şi B de lungimi n şi respectiv m. Complexitatea algoritmului LCS este O(nm). Pentru cazul particular din P6, există algoritmul Hunt-Szymanski care extinde ideea de rezolvare în O(n log n) a problemei P1, obţinând o complexitate O(R log n), unde R este numărul de potriviri, adică numărul de apariţii ale elementelor şirului A în şirul B. De fapt, o potrivire este un cuplu (p,q), cu proprietatea că Ap = Bq. Deoarece orice element din A apare de două ori în B, atunci numărul de potriviri este R = 2n. Să considerăm următorul exemplu: n=8, A = 4, 1, 3, 4, 2, 1, 2, 3 şi B = 1, 3, 1, 2, 4, 3, 4, 2. Potrivirile au loc la poziţiile: (1,5), (1,7), (2,1), (2,3), (3,2), (3,6), (4,5), (4,7), (5,4), (5,8), (6,3), (6,1), (7,8), (7,4), (8,6), (8,2). Vom ordona potrivirile crescător după poziţiile din şirul A şi apoi descrescător după poziţiile din vectorul B. Deci ordinea va fi următoarea: (1,7), (1,5), (2,3), (2,1), (3,6), (3,2), (4,7), (4,5), (5,8), (5,4), (6,3), (6,1), (7,8), (7,4), (8,6), (8,2). Construim vectorul LCS de lungime n, în care LCS[i] va reţine cel mai mic indice din vectorul B până la care se poate obţine un subşir comun de lungime i. Se iau cele R potriviri pe rând, iar în vectorul LCS vor fi memorate, cum am spus, numai indici din B. Analog ca la problema LIS rezolvată în O(n log n), valorile din vectorul LCS vor apărea tot timpul sortaţi crescător. Pentru fiecare potrivire (p,q) se face o căutare binară pentru q în LCS[1..max], unde max este numărul de componente ocupate în vector, determinându-se o poziţie i cu proprietatea că LCS[i-1] < q < LCS[i]. În acest caz, s-a găsit un indice q care este extremitatea dreaptă a unui subşir comun de lungime i, deci LCS[i] va reţine pe q. Dacă q > LCS[max], atunci subşirul comun se extinde cu 1, iar  în noua componentă va fi depus q. În tabelul de mai jos este descris modul de completare al vectorului LCS pentru exemplul dat anterior:

Subşirul comun maximal are lungimea 5. Ultima componantă ocupată din vectorul LCS, în exemplul nostru 6, ne indică şi cel mai mare indice din B unde s-a găsit ultimul element comun celor două subşiruri.
După cum se observă din exemplu, algoritmul are exact R = 2n paşi, pentru fiecare pas realizându-se o căutare binară. Vectorul LCS are, evident, lungimea maximă n. Numărul de operaţii este deci 2n*log n. Să mai notăm faptul că sortarea potrivirilor nu adaugă timp suplimentar, deoarece se poate face în timp liniar. Lăsăm scrierea algoritmului ca exerciţiu, considerând că exemplul dat este sugestiv.

Consideraţii finale
Apar destul de des în diverse concursuri probleme legate de determinarea subşirului crescător de lungime maximă sau variante ale acestuia. De exemplu, relaţia "<=" între elementele subşirului se poate schimba într-o relaţie oarecare. Aşa este problema Lanţ de la olimpiada judeţeană din 2005, clasele XI–XII. Problema P6 apare propusă la barajul pentru stabilirea lotului României la ONI 2001, dar în care, suplimentar, este cerută şi determinarea efectivă a subşirului comun de lungime maximă. Există de asemenea pe site-ul http://infoarena.ro şi alte probleme legate de problema LIS. O problemă care tratează un alt caz particular al problemei LCS este problema  Tabara de la etapa 3 a concursului .campion, ediţia 2003. Nu în ultimul rând recomandăm cititorilor o altă problemă clasică, cea legată de determinarea celui mai lung subşir comun crescător (Longest Common Increasing Subsequence – LCIS), al cărui algoritm de rezolvare este cunoscut sub numele de Algoritmul lui Chao şi are o complexitate pătratică.

Număr de accesări: 30505

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică