(toc){width: 27em}*{text-align:center} *Conţinut*
* 'Introducere ':probleme-cu-secvente#introducere

* 'Problema 1 (Subsecvenţa de sumă maximă) ':probleme-cu-secvente#problema-1
* 'Problema 2 (Maximum Sum) ':probleme-cu-secvente#problema-2
* 'Problema 3 (SequenceQuery) ':probleme-cu-secvente#problema-3

* 'Problema 1: Subsecvenţa de sumă maximă ':probleme-cu-secvente#problema-1
* 'Problema 2: Maximum Sum ':probleme-cu-secvente#problema-2
* 'Problema 3: SequenceQuery ':probleme-cu-secvente#problema-3

* 'Problema 4 ':probleme-cu-secvente#problema-4
* 'Problema 5 ':probleme-cu-secvente#problema-5

* 'Problema 6 (Secvenţă) ':probleme-cu-secvente#problema-6
* 'Problema 7 (Agricultura) ':probleme-cu-secvente#problema-7
* 'Problema 8 (Secvenţa 2) ':probleme-cu-secvente#problema-8
* 'Problema 9 (Sum) ':probleme-cu-secvente#problema-9
* 'Problema 10 (Secvenţa 3) ':probleme-cu-secvente#problema-10
* 'Problema 11 (XorMax) ':probleme-cu-secvente#problema-11

* 'Problema 6: Secvenţă ':probleme-cu-secvente#problema-6
* 'Problema 7: Agricultura ':probleme-cu-secvente#problema-7
* 'Problema 8: Secvenţa 2 ':probleme-cu-secvente#problema-8
* 'Problema 9: Sum ':probleme-cu-secvente#problema-9
* 'Problema 10: Secvenţa 3 ':probleme-cu-secvente#problema-10
* 'Problema 11: XorMax ':probleme-cu-secvente#problema-11

* 'Probleme propuse':probleme-cu-secvente#probleme-propuse
* 'Bibliografie':probleme-cu-secvente#bibliografie

Acest articol prezintă o serie de probleme înrudite cu problema subsecvenţei de sumă maximă, însoţite de rezolvări eficiente. Problemele prezentate pot apărea oricând ca subprobleme în concursurile de programare, studierea lor mărind în mod util bagajul de cunoştinţe al unui elev pasionat de algoritmică.

h2(#problema-1). Problema 1 (Subsecvenţa de sumă maximă)

h2(#problema-1). Problema 1: Subsecvenţa de sumă maximă

bq. Se dă un şir de $N$ numere întregi $(a{~1~}, a{~2~}, ..., a{~N~})$. Să se determine o subsecvenţă $(a{~i~}, a{~i+1~}, ..., a{~j~})$ care să aibă suma maximă.

}
==

h2(#problema-2). Problema 2 ('Maximum Sum':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44, UVa)

h2(#problema-2). Problema 2: 'Maximum Sum':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44 (UVa)

bq. Se dă o matrice de dimensiuni $N x N$ cu elemente întregi. Se cere determinarea unei submatrici a cărei elemente au suma maximă.

Cel mai bun algoritm cunoscut pentru această problemă are complexitatea <tex>O(N^{3\sqrt{\frac{\log \log N}{\log N}}})</tex> şi este mai mult un algoritm teoretic decât unul practic, uşor implementabil. Pentru detalii puteti consulta lucrarea [3].

h2(#problema-3). Problema 3 ('SequenceQuery':problema/sequencequery, Bursele Agora 2006)

h2(#problema-3). Problema 3: 'SequenceQuery':problema/sequencequery (Bursele Agora 2006)

bq. Se consideră un şir $A = (a{~1~}, a{~2~}, ..., a{~N~})$, format din numere întregi $(-100.000 ≤ a{~i~} ≤ 100.000)$, şi $M$ perechi de numere $(x, y)$ $(1 ≤ N, M ≤ 100.000)$. Pentru fiecare pereche ordonată de indici $(x, y)$ trebuie determinată subsecvenţa de sumă maximă a subşirului $a{~x~}, a{~x+1~}, ..., a{~y~}$. Subsecvenţele alese trebuie să conţină cel puţin un element.

În următorul desen observăm structura unui arbore de intervale pentru un şir cu $16$ elemente. Daca se pune întrebarea $[2, 11]$ acest interval va fi spart în intervalele $[2, 2], [3, 4], [5, 8], [9, 10], [11, 11]$.

!probleme-cu-secvente?numere2.png!

p=. !probleme-cu-secvente?numere2.png!

Prezentăm procedura de construire a arborelui, implementată în _java_:

Astfel putem face o căutare binară pentru a determina valoarea $X$ a mediei maxime. Ne mai rămâne să determinăm un algoritm eficient pentru găsirea subsecvenţei de sumă maximă de lungime cel puţin $F$. O asemenea soluţie urmăreşte una din ideile din prima problemă: fie $best[i]$ subsecvenţa de sumă maximă ce se termină în $a[i]$. Evident $best[i] = max(a[i], best[i - 1] + a[i])$. Acum secvenţa de sumă maximă ce se termină în $a[i]$, de lungime cel puţin $F$ se găseşte ca $a[i] + a[i - 1] + .. + a[i - F + 2] + best[i - F + 1]$. Această relaţie poate fi calculată în $O(1)$ dacă ne folosim de trucul sumelor parţiale. Complexitatea finală este $O(N * log C)$, unde $C$ e valoarea maximă a lui $a{~i~}$.

h2(#problema-6). Problema 6 ('Secvenţă':problema/secventa)

h2(#problema-6). Problema 6: 'Secvenţă':problema/secventa

bq. Se da un şir de $N$ numere întregi. O secvenţă este un subşir de numere care apar pe poziţii consecutive în şirul iniţial. Definim baza unei secvenţe ca fiind minimul valorilor elementelor din secvenţa respectivă. Fiind dat un număr natural $K$, determinaţi o secvenţă de lungime cel puţin $K$, cu baza maximă. Restrictii: $1 ≤ K ≤ N ≤ 500 000$.

lista devine: $(4, 6) (6, 8)$
elementul minim al secvenţei $a[6..8]$ este $4$

h2(#problema-7). Problema 7 (Agricultura, Algoritmus)

h2(#problema-7). Problema 7: Agricultura (Algoritmus)

bq. Se dă o matrice de dimensiuni $N x M$ de numere naturale. Se cere determinarea unei submatrici cu număr maxim de celule în care diferenţa între valoarea maximă şi valoarea minimă este mai mică decât o valoare dată $K$. Restrictii: $2 ≤ N, M ≤ 150$, $1 ≤ K ≤ 1 000$.

Problema constă în determinarea submatricei cu număr maxim de celule în care diferenţa între valoarea maximă şi valoarea minimă este mai mică decât $K$. Vom folosi ideea de la problema cu subsecvenţa de sumă maximă pe matrice, adică vom fixa două linii $i{~1~}$ şi $i{~2~}$. Acum pentru fiecare coloană $j$ păstrăm în $m[j]$ elementul minim şi în $M[j]$ elementul maxim $a[i][j]$ cu $i{~1~} ≤ i ≤ i{~2~}$. Astfel la fiecare pas trebuie acum să rezolvăm problema determinării unei subsecvenţe de lungime maximă pentru care diferenţa între elementul maxim şi minim este mai mică decât $K$. Folosind un _max-heap_ şi un _min-heap_ putem parcurge elementele şirurilor $M$ şi $m$ în ordine inserând la fiecare pas elemente în heap şi determinând cea mai lungă secvenţă ce se termină în $i$ cu proprietatea dată. Vom ţine un al $2$-lea indice $j$, iniţial $0$, care atâta timp cât diferenţa între elementul maxim din max-heap cu elementul minim din min-heap este mai mare sau egală cu $K$, vom scoate din heapuri elementele $M[j]$, respectiv $m[j]$ şi îl vom incrementa pe $j$. Complexitate: $O(N^3^ log N)$. Dacă în loc de heapuri folosim deque-uri, atunci acest algoritm va avea complexitatea $O(N^3^)$.

h2(#problema-8). Problema 8 ('Secvenţa 2':problema/secv2)

h2(#problema-8). Problema 8: 'Secvenţa 2':problema/secv2

bq. Se da un şir de $N$ numere întregi şi un număr natural $K$. O secvenţă este un subşir de numere care apar pe poziţii consecutive în şirul iniţial. Se cere să se găsească secvenţa de sumă maximă de lungime cel puţin $K$. Restrictii: $1 ≤ K ≤ N ≤ 50 000$.

Putem folosi rezolvarea liniară bazată pe programare dinamică prezentată ca subalgoritm în soluţia 'problemei $5$':probleme-cu-secvente#problema-5, dar putem simplifica logica din acea rezolvare. Vom folosi şirul sumelor parţiale $sum[]$, iar pentru a determina subsecvenţa de sumă maximă ce se termină în $i$ şi are lungimea cel puţin $K$ trebuie să găsim $sum[j]$ minim astfel ca $j < i - K$. Parcurgem lista, şi la pasul $i$ determinăm $best[i] = sum[i] - min(sum[j])$, $j < i - K$. Comparăm minimul curent cu $sum[i - K]$ şi trecem la pasul următor. Complexitate: $O(N)$.

h2(#problema-9). Problema 9 ('Sum':problema/sum2, Stelele Informaticii 2003 )

h2(#problema-9). Problema 9: 'Sum':problema/sum2 (Stelele Informaticii 2003)

bq. Se dă un şir de $N$ numere întregi. Se caută un subşir cu lungimea cuprinsă între $L$ şi $U$, format din elemente consecutive ale şirului iniţial, cu suma elementelor maximă. Restrictii: $1 ≤ L ≤ U ≤ N ≤ 100 000$.

Pentru fiecare element din partiţie ţinem minte un pointer $p[i]$ spre ultimul element din subsecvenţa din care face parte. Fiecare interval $[i, p[i]]$ va corespunde celei mai scurte subsecvenţe care începe în $i$ şi are suma pozitivă. Pentru a determina o soluţie a problemei pentru fiecare $i$ din care poate începe o subsecvenţă de sumă maximă, ne vom plimba cu un pointer $j$ astfel ca $j$ să fie cât mai depărtat de $i$ şi $j - i + 1 ≤ U$. Obţinem astfel de fiecare dată o subsecvenţă de sumă maximă ce începe în $i$, cu lungimea mai mică sau egală cu $U$. Indicele $j$ va fi întotdeauna un capăt de secvenţă negativă la stânga şi la fiecare mărire a lui $i$ verificăm dacă lui $j$ îi putem atribui valoarea $p[j + 1]$ ( adică dacă $p[j + 1] - i + 1 ≤ U$ ). Dacă secvenţa de sumă maximă de lungime cel mult $U$ ce începe în $i$ are lungimea mai mică decât $L$, atunci secvenţa de sumă maximă cu lungimea cuprinsă între $L$ şi $U$ are lungimea exact $L$. Complexitate: $O(N)$.

h2(#problema-10). Problema 10 ('Secvenţa 3':problema/secv3)

h2(#problema-10). Problema 10: 'Secvenţa 3':problema/secv3

bq. Se dă un şir de $N$ elemente pentru care se cunosc două informaţii: costul şi timpul. O secvenţă este un subşir de numere care apar pe poziţii consecutive în şirul iniţial. Se caută o secvenţă din cele $N$ elemente care să fie de lungime minim $L$ şi maxim $U$, iar suma costurilor elementelor secvenţei împărţiţă la suma timpurilor elementelor secvenţei să fie maximă. Restrictii: $1 ≤ L ≤ U ≤ N ≤ 30 000$.

Procedăm ca la 'problema $5$':probleme-cu-secvente#problema-5 şi căutăm binar valoarea optimă. şirul va fi transformat în: $b[i] = c[i] - t[i] * X$, $i = 1..N$. Acum trebuie să mai rezolvăm subproblema care cere să determinăm o subsecvenţă de sumă maximă pentru care lungimea se află între $L$ şi $U$. Această subproblemă a fost soluţionată în 'problema anterioară':probleme-cu-secvente#problema-9, unde s-a găsit un algoritm liniar. Astfel soluţia acestei probleme are complexitatea $O(N * log C)$.

h2(#problema-11). Problema 11 ('XorMax':problema/xormax)

h2(#problema-11). Problema 11: 'XorMax':problema/xormax

bq. Se dă un şir de $N$ numere întregi nenegative. Să se aleagă o secvenţă a şirului, $(a{~i~}, a{~i+1~}, ..., a{~j~})$, astfel încât $a{~i~} xor a{~i+1~} xor ... xor a{~j~}$ să fie maxim. Restrictii: $1 &le; N &le; 100 000$ si $a{~i~} < 221$ cu $i = 1..N$.