== include(page="template/implica-te/scrie-articole-2" user_id1="alecman" user_id2="Marius") ==

(Categoria _Diverse_, Autor _Cosmin Negruşeri_)

(Categoria _Algoritmi şi tehnici de programare_, Autor _Cosmin Negruşeri_)

(toc){width: 30em}*{text-align:center} *Cuprins*
* 'Introducere ':probleme-cu-secvente#intro
* 'Problema 1 (Subsecvenţa de sumă maximă) ':probleme-cu-secvente#prob1
* 'Problema 2 (Maximum Sum) ':probleme-cu-secvente#prob2
* 'Problema 3 (SequenceQuery) ':probleme-cu-secvente#prob3
* 'Problema 4 ':probleme-cu-secvente#prob4
* 'Problema 5 ':probleme-cu-secvente#prob5
* 'Problema 6 (Secvenţă) ':probleme-cu-secvente#prob6
* 'Problema 7 (Agricultura) ':probleme-cu-secvente#prob7
* 'Problema 8 (Secvenţa 2) ':probleme-cu-secvente#prob8
* 'Problema 9 (Sum) ':probleme-cu-secvente#prob9
* 'Problema 10 (Secvenţa 3) ':probleme-cu-secvente#prob10
* 'Problema 11 (XorMax) ':probleme-cu-secvente#prob11
* 'Probleme propuse':probleme-cu-secvente#probp

(toc){width: 30em}*{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 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
* 'Probleme propuse':probleme-cu-secvente#probleme-propuse

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

h2(#intro). Introducere

h2(#introducere). Introducere

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(#prob1). 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ă.

== code(cpp) |
sum[0] = 0;

for (i = 1; i ≤ N; i++) sum[i] = a[i] + sum[i-1];

for (i = 1; i <= N; i++) sum[i] = a[i] + sum[i-1];

min = sum[0];
bestSum = -INFINIT;

for (i = 1; i ≤ N; i++) {

for (i = 1; i <= N; i++) {

    best[i] = sum[i] - min;
    if (min > sum[i]) min = sum[i];
    if (bestSum < best[i]) bestSum = best[i];

    pre = 0;
    maxSuf = -INFINIT;
    maxPre = -INFINIT;

    for (i = mid; i ≥ l; i--) {

    for (i = mid; i >= l; i--) {

        suf += a[i];
        if (maxSuf < suf) maxSuf = suf;
    }

    for (i = mid + 1; i ≤ r; i++) {

    for (i = mid + 1; i <= r; i++) {

        pre += a[i];
        if (maxPre < pre) maxPre = pre;
    }

== code(cpp) |
sum = -INFINIT;
bestSum = -INFINIT;

for (i = 1; i ≤ N; i++) {

for (i = 1; i <= N; i++) {

    sum += a[i];
    if (sum < 0)
        sum = 0;

    else if (sum ≥ bestSum)

    else if (sum >= bestSum)

        bestSum = sum;
}
==

h2(#prob2). 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(#prob3). Problema 3 ('SequenceQuery':problema/sequencequery, Bursele Agora 2005/2006 Runda 1)

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

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.

h3. Exemplu:
Pentru şirul $(-1, 2, 3, -2, 4, -3, 8, -3)$ şi intervalele $[1, 5]$, $[4, 8]$ si $[6, 6]$ avem soluţiile:

|_. $a$ | - | $-1$ | $2$ | $3$ | $-2$ | $4$ | $-3$ | $8$ | $-3$ | $1$ |
|_. $sum$ | $0$ | $-1$ | $1$ | $4$ | $2$ | $6$ | $3$ | $11$ | $8$ | $9$ |

Şirul e împărţit în trei subsecvenţe $[-1, 2, 3], [-2, 4, -3], [8, -3, 1]$:

şirul e împărţit în trei subsecvenţe $[-1, 2, 3], [-2, 4, -3], [8, -3, 1]$:

|_. $max$ | $4$ | $6$ | $11$ |
|_. $min$ | $-1$ | $2$ | $8$ |

}
==

Şi procedura care răspunde la întrebări tot în _java_:

şi procedura care răspunde la întrebări tot în _java_:

== code(java) |
long minPrefix;

Autorul vă recomandă articolele [1] şi [2] pentru o înţelegere mai profundă a structurii de date numită arbori de intervale. Problema poate fi soluţionată şi în $O(N + M)$, dar algoritmul este mult prea complicat pentru un concurs de programare; cei interesaţi pot să îl găsească în [4].

h2(#prob4). Problema 4 (ACM ICPC NWERC 97, olimpiada online 2000, campion 2001)

h2(#problema-4). Problema 4 (ACM ICPC NWERC 97, olimpiada online 2000, campion 2001)

bq. Se dă un şir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din numere întregi. Se cere să se determine subsecvenţa $a[i..j]$ care are modulul sumei elementelor minim.

O secvenţă de modul $2$ ar fi cea reprezentată de sumele $8$ şi $10$, cu indicii $7$ şi $2$. Această secvenţă este $(-6, -6, 9, 4, -3)$. Observăm ca cea mai mică diferenţă între termeni consecutivi e cea dintre $8$ şi $7$, care au indicii $7$ şi $5$, de unde obţinem că subsecvenţa de modul minim este $(4, -3)$.

h2(#prob5). Problema 5 (USACO)

h2(#problema-5). Problema 5 (USACO)

bq. Se dă un şir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din $N (1 ≤ N ≤ 100 000)$ numere întregi $(1 ≤ a{~i~} ≤ 2 000)$ si un numar natural $F$. Se cere să se determine subsecvenţa $a[i..i + K - 1]$ cu media aritmetică a elementelor maximă, unde $K$ are proprietatea $K ≥ F$.

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(#prob6). 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(#prob7). 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(#prob8). 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$.

h3. Rezolvare:

Putem folosi rezolvarea liniară bazată pe programare dinamică prezentată ca subalgoritm în soluţia 'problemei $5$':probleme-cu-secvente#prob5, 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)$.

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(#prob9). 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(#prob10). 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$.

h3. Rezolvare:

Procedăm ca la 'problema $5$':probleme-cu-secvente#prob5 ş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#prob9, unde s-a găsit un algoritm liniar. Astfel soluţia acestei probleme are complexitatea $O(N log C)$.

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(#prob11). 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$.

Suma _xor_ a două numere este de fapt adunare binară fără transport, fapt care o face similară operaţiei _modulo_. Problema e asemănătoare cu cea a subsecvenţei de modul maxim. Vom obţine toate sumele _xor_ parţiale şi pentru a vedea pentru $sum[i]$ perechea optimă cu care crează o sumă cât mai mare trebuie să găsim acea sumă $sum[j]$ astfel că fiecare bit al lui $sum[i]$ să fie diferit de fiecare bit al lui $sum[j]$, dacă acest lucru este posibil. Pentru a face această căutare cât mai eficientă, putem menţine sumele $sum[i]$ ca şiruri de caractere $0$ sau $1$ într-un _trie_ [5]. Structura de trie pentru cazul când alfabetul are dimensiunea $2$ este identică cu cea de heap. Această soluţie are complexitatea $O(N log C)$.

h2(#probp). Probleme propuse

h2(#problema-propuse). Probleme propuse

Pentru a vă însuşi mai bine tehnicile învăţate în acest articol, autorul vă sugerează să rezolvaţi următoarele probleme: