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

h3. Rezolvare:

Putem folosi trucul construirii sumelor parţiale din rezolvarea anterioară, pentru cazul $2D$. Păstrăm în $sum[i][j]$ suma tuturor elementelor $a[i{~1~}][j{~1~}]$ cu proprietatea că $1 <= i{~1~} <= i$, şi $1 <= j{~1~} <= j$. Putem calcula sumele prin metoda programării dinamice în complexitate $O(N^2^)$ folosind formula: $sum[i][j] = a[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]$. Acum, pentru a calcula suma elementelor din matricea cu colţurile $(i{~1~}, j{~1~})$ şi $(i{~2~}, j{~2~})$, unde $i{~1~} <= i{~2~}$ şi $j{~1~} <= j{~2~}$, este suficient să facem calculul $sum[i{~2~}][j{~2~}] - sum[i{~1~}-1][j{~2~}] - sum[i{~2~}][j{~1~}-1] + sum[i{~1~}-1][j{~1~}-1]$. Astfel putem evalua suma din fiecare submatrice în timp constant, deci rezolvarea are ordinul de complexitate $O(N^4^)$.

Putem folosi trucul construirii sumelor parţiale din rezolvarea anterioară, pentru cazul $2D$. Păstrăm în $sum[i][j]$ suma tuturor elementelor $a[i{~1~}][j{~1~}]$ cu proprietatea că $1 ≤ i{~1~} ≤ i$, şi $1 ≤ j{~1~} ≤ j$. Putem calcula sumele prin metoda programării dinamice în complexitate $O(N^2^)$ folosind formula: $sum[i][j] = a[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]$. Acum, pentru a calcula suma elementelor din matricea cu colţurile $(i{~1~}, j{~1~})$ şi $(i{~2~}, j{~2~})$, unde $i{~1~} ≤ i{~2~}$ şi $j{~1~} ≤ j{~2~}$, este suficient să facem calculul $sum[i{~2~}][j{~2~}] - sum[i{~1~}-1][j{~2~}] - sum[i{~2~}][j{~1~}-1] + sum[i{~1~}-1][j{~1~}-1]$. Astfel putem evalua suma din fiecare submatrice în timp constant, deci rezolvarea are ordinul de complexitate $O(N^4^)$.

O altă idee ar fi ca pentru fiecare pereche $(i{~1~}, i{~2~})$ fixată să determinăm perechea optimă $(j{~1~}, j{~2~})$. Dacă avem liniile $i{~1~}$ şi $i{~2~}$ fixate atunci problema se transformă din una bidimensională în una unidimensională. Astfel pentru fiecare coloană $j$ vom considera $b[j]$ ca sumă a elementelor $a[i][j]$ cu proprietatea că $i{~1~} <= i <= i{~2~}$. În exemplul nostru, dacă $i{~1~} = 2$ şi $i{~2~} = 3$, atunci avem: $b{~1~} = 9 + (-4)$, $b{~2~} = 2 + 1$, $b{~3~} = (-6) + (-4)$ şi $b{~4~} = 2 + 1$. Pentru a rezolva problema unidimensională folosim unul din algoritmii liniari prezentaţi mai sus, astfel obţinându-se un algoritm de complexitate totală $O(N^3^)$. Acest truc de a fixa două linii pentru a transforma problema în una unidimensională este util în multe probleme pe matrice sau cu puncte în plan.

O altă idee ar fi ca pentru fiecare pereche $(i{~1~}, i{~2~})$ fixată să determinăm perechea optimă $(j{~1~}, j{~2~})$. Dacă avem liniile $i{~1~}$ şi $i{~2~}$ fixate atunci problema se transformă din una bidimensională în una unidimensională. Astfel pentru fiecare coloană $j$ vom considera $b[j]$ ca sumă a elementelor $a[i][j]$ cu proprietatea că $i{~1~} ≤ i ≤ i{~2~}$. În exemplul nostru, dacă $i{~1~} = 2$ şi $i{~2~} = 3$, atunci avem: $b{~1~} = 9 + (-4)$, $b{~2~} = 2 + 1$, $b{~3~} = (-6) + (-4)$ şi $b{~4~} = 2 + 1$. Pentru a rezolva problema unidimensională folosim unul din algoritmii liniari prezentaţi mai sus, astfel obţinându-se un algoritm de complexitate totală $O(N^3^)$. Acest truc de a fixa două linii pentru a transforma problema în una unidimensională este util în multe probleme pe matrice sau cu puncte în plan.

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)

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.

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:

Putem obţine un algoritm de complexitate $O(M * N)$ folosind algoritmii liniari din prima problemă, dar să vedem cum putem reduce complexitatea folosind alte abordări. Mai întâi calculăm şirul $sum[]$ al sumelor parţiale, după care împărţim şirul în $K$ subsecvenţe de lungimi egale $[N / K]$, şi păstrăm următoarele informaţii pentru fiecare din ele:

* $max[i]$ - cea mai mare valoare $sum[j]$, unde: $N/K * (i - 1) < j <= N/K * i$;

* $max[i]$ - cea mai mare valoare $sum[j]$, unde: $N/K * (i - 1) < j &le; N/K * i$;

* $min[i]$ - cel mai mic $sum[j - 1]$, unde: $N/K * (i - 1) < j <= N/K * i$;

* $min[i]$ - cel mai mic $sum[j - 1]$, unde: $N/K * (i - 1) < j &le; N/K * i$;

* $best[i]$ - valoarea subsecventei de suma maxima a secventei curente.

|_. $min$ | $-1$ | $2$ | $8$ |
|_. $best$ | $5$ | $4$ | $8$ |

Pentru a răspunde la întrebarea $[1, 5]$ trebuie să răspundem la cele două subsecvenţe componente $[1..3]$ şi $[4..5]$. Soluţia optimă pentru $[1..3]$ este $best[&#49;] = 5$. Soluţia optimă pentru $[4..5]$ o determinăm folosind algoritmul liniar, ea fiind $4$. Acum, pentru a determina subsecvenţa de sumă maximă cu câte un capăt în fiecare interval folosim formula: $max(sum[i]) - min(sum[j - 1])$, unde $4 <= i <= 5$ şi $1 <= j <= 3$. Valoarea $max(sum[i])$ o găsim parcurgând intervalul $[4, 5]$ ca fiind $6$, iar valoarea $min(sum[j - 1])$ o avem deja calculată în $min[&#49;]$. De aici obţinem rezultatul $7$.

Pentru a răspunde la întrebarea $[1, 5]$ trebuie să răspundem la cele două subsecvenţe componente $[1..3]$ şi $[4..5]$. Soluţia optimă pentru $[1..3]$ este $best[1] = 5$. Soluţia optimă pentru $[4..5]$ o determinăm folosind algoritmul liniar, ea fiind $4$. Acum, pentru a determina subsecvenţa de sumă maximă cu câte un capăt în fiecare interval folosim formula: $max(sum[i]) - min(sum[j - 1])$, unde $4 ≤ i ≤ 5$ şi $1 ≤ j ≤ 3$. Valoarea $max(sum[i])$ o găsim parcurgând intervalul $[4, 5]$ ca fiind $6$, iar valoarea $min(sum[j - 1])$ o avem deja calculată în $min[1]$. De aici obţinem rezultatul $7$.

O soluţie similară poate fi obţinută cu ajutorul arborilor de intervale. Mai întâi creăm arborele de intervale. Pentru fiecare interval aflăm elementele $min$, $max$ şi $best$ astfel:

long minPrefix;
int x, y;
public long queryTree(int index, int low, int high) {

    if (x <= low && high <= y) {

    if (x ≤ low && high ≤ y) {

        long maxRet = aint[index].maxS;
        if (minPrefix != infinity) {
            maxRet = Math.max(maxRet, aint[index].max - minPrefix);

    }
    else {
        int mid = (low + high) / 2;

        if (x <= mid && mid < y) return  Math.max(queryTree(2 * index, low, mid), queryTree(2 * index + 1, mid + 1, high));

        if (x &le; mid && mid < y) return  Math.max(queryTree(2 * index, low, mid), queryTree(2 * index + 1, mid + 1, high));

        else if (x > mid) return queryTree(2 * index + 1, mid + 1, high);
            else return queryTree(2 * index, low, mid);
    }

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

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$.

h3. Exemplu:

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

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$.

h3. Exemplu:

Acum putem face o parcurgere a şirului pentru a rezolva problema. Mai întâi punem într-un $min-heap$ $K$ elemente, verificăm vârful heapului şi obţinem astfel minimul secvenţei $a[1..K]$. Apoi eliminăm elementul $a[1]$ din heap şi inserăm elementul $a[K + 1]$. Prin verificarea vârfului heapului obţinem minimul secvenţei $a[2..K + 1]$. Continuăm procedeul până aflăm elementul minim pentru fiecare subsecvenţă de lungime $K$ a şirului $a$ (complexitate $O(N log K)$). Există şi alte soluţii pentru găsirea elementului minim al unei subsecvenţe, precum folosirea unui arbore de intervale sau folosirea tehnicii $O(N log N)/O(1)$ pentru problema _RMQ_.

O observaţie importantă este aceea că dacă vrem să vedem minimul secvenţei ce se termină în $i$ şi avem $j{~1~} < j{~2~} <= i$ şi $a[j{~1~}] >= a[j{~2~}]$, atunci evident $a[j{~1~}]$ nu va fi minimul secvenţei ce se termină în $i$. Folosim o structură de date ca la soluţia cu heapuri, care adaugă elemente noi şi şterge elemente vechi, dar pe lângă elementele ce au fost inserate acum $K$ paşi şi trebuie şterse, mai ştergem şi elementele mai noi care nu ne vor mai fi utile, după cum este $a[j{~2~}]$ mai sus. Ca structură de date folosim o listă în care putem insera şi şterge de la ambele capete, un _deque_. Fiecare element inserat în deque va fi o pereche de valori, valoarea din şir şi indexul din şir $(a[i], i)$. Când o valoare este inserată în şir, ea este pusă la capătul din dreapta al şirului, dar înainte de inserare cât timp elementul din capătul şirului are valoarea mai mare decât $a[i]$ el este eliminat. La fiecare pas după o inserţie se verifică dacă elementul din capătul din stânga este mai „bătrân” de $K$ iteraţii.

O observaţie importantă este aceea că dacă vrem să vedem minimul secvenţei ce se termină în $i$ şi avem $j{~1~} < j{~2~} &le; i$ şi $a[j{~1~}] &ge; a[j{~2~}]$, atunci evident $a[j{~1~}]$ nu va fi minimul secvenţei ce se termină în $i$. Folosim o structură de date ca la soluţia cu heapuri, care adaugă elemente noi şi şterge elemente vechi, dar pe lângă elementele ce au fost inserate acum $K$ paşi şi trebuie şterse, mai ştergem şi elementele mai noi care nu ne vor mai fi utile, după cum este $a[j{~2~}]$ mai sus. Ca structură de date folosim o listă în care putem insera şi şterge de la ambele capete, un _deque_. Fiecare element inserat în deque va fi o pereche de valori, valoarea din şir şi indexul din şir $(a[i], i)$. Când o valoare este inserată în şir, ea este pusă la capătul din dreapta al şirului, dar înainte de inserare cât timp elementul din capătul şirului are valoarea mai mare decât $a[i]$ el este eliminat. La fiecare pas după o inserţie se verifică dacă elementul din capătul din stânga este mai „bătrân” de $K$ iteraţii.

Din cauza modului în care se fac inserţiile şi ştergerile, şirul va fi sortat totdeauna crescător după indecşi şi crescător după valori. Tot timpul ultimul element din stivă va conţine valoarea bazei. Acest algoritm are complexitatea $O(N)$ pentru că fiecare element este inserat şi şters din deque cel mult o dată.

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

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$.

h3. Exemplu:

h3. Rezolvare:

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^)$.

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)

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$.

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. Exemplu:

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

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$.

h3. Rezolvare:

Pentru fiecare $i$ este de ajuns să aflăm valoarea expresiei $sum[i] - sum[j]$, unde $i - L > j >= i - U$. Pentru a determina valoarea optimă pentru $sum[j]$ putem folosi un heap de dimensiune $U - L$, sau putem folosi tehnici de determinare a valorii minime într-un interval dat. Complexitate: $O(N log(U - L))$.

Pentru fiecare $i$ este de ajuns să aflăm valoarea expresiei $sum[i] - sum[j]$, unde $i - L > j ≥ i - U$. Pentru a determina valoarea optimă pentru $sum[j]$ putem folosi un heap de dimensiune $U - L$, sau putem folosi tehnici de determinare a valorii minime într-un interval dat. Complexitate: $O(N log(U - L))$.

Altă abordare de aflare a minimelor unor secvenţe de lungime dată (în cazul acesta lungimea este $U - L$ ) a fost prezentată în rezolvarea 'problemei $6$':probleme-cu-secvente@prob6. Folosind acea tehnică obţinem o rezolvare de complexitate liniară.
O altă rezolvare frumoasă prezentată în [4] este următoarea: spunem că o secvenţă este negativă spre stânga dacă suma oricărui prefix ( în afară de secvenţa în sine ) al secvenţei este negativ sau zero. O partiţie a secvenţei $A = (A{~1~}, A{~2~}, ..., A{~k~})$ este minimală negativă spre stânga dacă fiecare $A{~i~}$ este negativă spre stânga, iar suma elementelor lui $A{~i~}$ este strict pozitivă dacă $i != k$. De exemplu secvenţa $(-4, 1, -2, 3)$ este negativă la stânga, pe când secvenţa $(5, -3, 4, -1, 2, -6)$ nu este. Partiţia $(5) (-3, 4) (-1, 2) (-6)$ este minimală negativă la stânga.

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)$.

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)

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$.

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. Exemplu:

h2(#prob11). 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 <= N <= 100 000$ si $a{~i~} < 221$ cu $i = 1..N$.

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$.

h3. Exemplu:

4. Kuan Yu Chen, Kun Mao Chao, _On the Range Maximum-Sum Segment Query_
5. Yaw Ling Liu, Tao Jiang, Kun Mao Chao, _Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecolar Sequence Analysis_
6. Vladu Adrian, Negruşeri Cosmin, Ginfo Noiembrie 2005

7. T. H. Cormen, C. E. Leiserson, R. R. Rivest - '_Introducere in Algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm
 

7. T. H. Cormen, C. E. Leiserson, R. R. Rivest - '_Introducere in Algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm