Probleme cu secvenţe

(Categoria Diverse, autor Cosmin Negruşeri)

• Cuprins
• Introducere
• Problema 1 ( Subsecvenţa de sumă maximă )
• Problema 2 (Maximum Sum) - 104 acm.uva.es
• Problema 3 (Interogare) - Bursele Agora 2005/2006 Runda 1

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

Problema 1 ( Subsecvenţa de sumă maximă )

Se dă un şir de N numere întregi (a₁, a₂, ..., a_N). Să se determine o subsecvenţă (a_i, a_i+1, ..., a_j) care să aibă suma maximă.

Exemplu

Pentru secvenţa de numere (-1, 2, 3, -4, -2, 2, 1, -3, -2, -3, -4, 9, -2, 1, 7, 8, -19, -7, 2, 4, 3), o subsecvenţă de sumă maximă este (9, -2, 1, 7, 8).

Rezolvare

Prima rezolvare care ne vine în minte are complexitatea O(N³) şi constă în determinarea sumei fiecărei subsecvenţe posibile şi reţinerea maximului acestor sume. Este evident că anumite sume parţiale sunt calculate de mai multe ori.

Putem reduce complexitatea la O(N²) ţinând cont de faptul că suma subsecvenţei a[i..j] este egală cu suma subsecvenţei a[i..j-1], la care se adună a[j]. Păstrăm într-un şir sum[i] - suma elementelor din subsecvenţa a[1..i]. Pentru a determina suma elementelor din subsecvenţa a[i..j] facem diferenţa sum[i] - sum[j-1].

Ideea poate fi rafinată calculând pentru fiecare indice i numărul best[i], reprezentând subsecvenţa de sumă maximă cu capătul drept în i. Este uşor de observat că best[i] = max(sum[i] - sum[j-1]), unde j ia valori de la 1 la i. Relaţia anterioară se mai poate scrie best[i] = sum[i] - min(sum[j-1 ]). Obţinem astfel un algoritm liniar care ne determină subsecvenţa de sumă maximă cerută.

sum[0] = 0;
for (i = 1; i <= N; i++) sum[i] = a[i] + sum[i-1];
min = sum[0];
bestSum = -INFINIT;
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];
}

O altă metodă de calcul poate fi dedusă folosind paradigma Divide Et Impera. La fiecare pas împărţim şirul în jumătate şi aflăm subsecvenţele de sumă maximă din cele două jumătăţi. După aceea trebuie să găsim subsecvenţa de sumă maximă ce are un capăt în fiecare din cele două jumătăţi ale sirului. Pentru aceasta alipim sufixul de sumă maximă a primei jumătăţi cu prefixul de sumă maximă a celei de-a doua.

int getMaxSubsequence(int l, int r) {
    if (l == r) return a[l];
    mid = (l + r) / 2;
    bestL = getMaxSubsequence(l, mid);
    bestR = getMaxSubsequence(mid + 1, r);
    suf = 0; 
    pre = 0; 
    maxSuf = -INFINIT; 
    maxPre = -INFINIT;
    for (i = mid; i >= l; i--) {
        suf += a[i];
        if (maxSuf < suf) maxSuf = suf;
    }
    for (i = mid + 1; i <= r; i++) {
        pre += a[i];
        if (maxPre < pre) maxPre = pre;    
    }
    return max(bestL, max(bestR, maxPre + maxSuf));
}

O idee bazată pe paradigma programării dinamice ar fi să folosim un şir best[ i ], reprezentând suma maximă a unei subsecvenţe ce se termină în a[i]. Problema se rezolvă cu următoarea formulă de recurenţă: best[i] = max(a[i], best[i-1] + a[i]). Formula poate fi demonstrată prin inducţie matematică.

O ultimă idee ar fi să partiţionăm şirul în subsecvenţe încât fiecare să aibă ambele capete cât mai mici posibile şi suma elementelor subsecvenţei să fie negativă. Pentru exemplul dat avem următoarea partiţionare [-1], [2, 3, -4, -2], [2, 1, -3, -2], [-3], [-4], [9, -2, 1, 7, 8, -19, -7], [2, 4, 3]. O subsecvenţă de sumă maximă va avea primul capăt la începutul unei astfel de subsecvenţe, acest lucru explicându-se prin faptul că în caz contrar secvenţa poate fi mărită în stânga (orice secvenţă din cele alese pentru partiţionare are toate prefixele de sumă pozitivă, în afară de prefixul ce reprezintă întreaga subsecvenţă). De asemenea, orice subsecvenţă de sumă maximă nu va conţine elemente din altă parte a partiţiei, pentru că dacă subsecvenţa se întinde pe mai multe părţi, atunci putem elimina prefixul subsecvenţei care reprezintă o parte a partiţiei, acea parte având suma negativă.

sum = -INFINIT;
bestSum = -INFINIT;
for (i = 1; i <= N; i++) {
    sum += a[i];
    if (sum < 0) {
        sum = 0;
        continue;
    } else 
    if (sum >= bestSum) bestSum = sum;      
}

Problema 2 ( Maximum Sum )

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

Exemplu

Pentru matriceasubmatricea de sumă maximă este următoarea:

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₁][j₁] cu proprietatea că 1 <= i₁ <= i, şi 1 <= j₁ <= j. Putem calcula sumele prin metoda programării dinamice (complexitate O(N²)) 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₁, j₁) şi (i₂, j₂), unde i₁ <= i₂ şi j₁ <= j₂, este suficient să facem calculul sum[i₂][j₂] - sum[i₁-1][j₂] - sum[i₂][j₁-1] + sum[i₁-1][j₁-1]. Astfel putem evalua suma din fiecare submatrice în timp constant, deci rezolvarea are ordinul de complexitate O(N⁴).

O altă idee ar fi ca pentru fiecare pereche (i₁, i₂) fixată să determinăm perechea optimă (j₁, j₂). Dacă avem liniile i₁ şi i₂ 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₁ <= i <= i₂. În exemplul nostru, dacă i₁ = 2 şi i₂ = 3, atunci avem b₁ = 9 + (-4), b₂ = 2 + 1, b₃ = (-6) + (-4) şi b₄ = 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³). 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 si este mai mult un algoritm teoretic decat unul practic, usor implementabil.

Problema 3 (Interogare) - Bursele Agora 2005/2006 Runda 1

Se considera un sir A = (a₁, a₂, ..., a_N) (-100.000 <= a_i <= 100.000), format din N numere intregi, precum si M perechi de numere (x, y) (1 <= N, M <= 100.000). Pentru fiecare pereche de indici (x, y) (1 <= x <= y <= N) trebuie determinata subsecventa de suma maxima a subsirului a_x, a_x+1, ..., a_y , subsecventele alese trebuie ss contins cel putin un element.

Exemplu

Pentru sirul (-1, 2, 3, -2, 4, -3, 8, -3, 1) si intervalele [1, 5], [4, 8] si [6, 6] avem solutiile 7, 9, -3, date de numerele ingrosate ([-1, 2, 3, -2, 4], -3, 8, -3, 1, -1, 2, 3, [-2, 4, -3, 8, -3], 1, -1, 2, 3, -2, 4, -3, 8, -3, 1).

Rezolvare

Folosind algoritmii liniari din prima problema obtinem un algoritm de complexitate O(MN). Sa vedem cum putem reduce complexitatea folosind alte abordari. Mai intai calculam sirul sum al sumelor partiale. Apoi impartim sirul in k subsecvente de lungimi egale [n/k], pentru fiecare secventa pastrand urmatoarele informatii:
* max[i] - cea mai mare valoare sum[j], unde n/k * (i-1) < j <= n/k * i;
* min[i] - cel mai mic sum[j-1], unde n/k * (i-1) < j <= n/k * i;
* best[i] - valoarea subsecventei de suma maxima a secventei curente.
Acum, daca vrem sa aflam subsecventa de suma maxima a subsecventei a[x..y], avem doua cazuri posibile:
1. Daca elementele de indice x si y apartin aceleiasi subsecvente din partitie, atunci putem gasi subsecventa de suma maxima folosind algoritmul liniar direct pe sirul a[x..y] (complexitate O(n/k)).
2. Daca ele nu sunt in aceeasi secventa atunci vom imparti sirul a[x..y] in un prefix de subsecventa din cele ce apartin partitionarii, in un sufix de subsecventa si in zero sau mai multe subsecvente complete ce apartin partitionarii. Acum vom rezolva problema pentru sufix si prefix metoda liniara ( O(n/k) ), iar apoi in O(1) vom determina pentru fiecare bucata în care este spart sirul a[x..y], subsecventa ei de suma maxima.
Mai ramane sa gasim subsecventa de suma maxima cu capatul in bucati diferite. Pentru doua bucati fixate i <= j, subsecventa de suma maxima ce are un capat apartinand primei bucati si j apartinand celei de a doua bucati, subsecventa de suma maxima are valoarea max[j] – min[i]. Determinarea subsecventei de suma maxima cu capetele in bucati diferite devine astfel de complexitate O(k). Deci pentru a rezolva o intrebare trebuie sa facem O(n/k + k) calcule. Pentru a reduce complexitatea problemei obtinem pe k = sqrt(n). Complexitatea totala a acestei solutii este O(N + M sqrt(N)).

Sa vedem ce se intampla pe exemplu:
a:  -1 2 3 -2 4 -3 8 -3 1
sum: 0 -1 1 4 2 6 3 11 8 9

Sirul e impartit in trei subsecvente [-1, 2, 3], [-2, 4, -3], [8, -3, 1].
max: $ 4 6 11$
min: $-1 2 8$
best: $ 5 4 8$
Pentru a raspunde la intrebarea [1, 5] vedem ca acest interval e inpartit in [1..3] si [4..5]. Solutia optima pentru [1..3] o avem deja in best¹ = 5. Solutia optima pentru [4..5] o determinam folosind algoritmul liniar, ea fiind 4. Acum pentru a determina subsecventa de suma maxima cu un capat in intervalul [1, 3] si celalalt in intervalul [4, 5] folosim max(sum[i]) - min(sum[j-1]), unde 4 <= i <= 5 si 1 <= j <= 3. Valoarea max(sum[i]) o gasim ca fiind 6 parcurgand intervalul [4, 5], iar valoarea min(sum[j-1]) o avem deja calculata in min¹. De aici obtinem rezultatul 7.

O solutie similara poate fi realizata cu ajutorul arborilor de intervale. Mai intai cream arborele de intervale. Pentru fiecare interval aflam elementele min, max si best astfel min[x..y] = minim(min[x..(x+y)/2], min[(x+y)/2 + 1 .. y]), max[x..y] = maxim(max[x..(x+y)/2], max[(x+y)/2 + 1 .. y]), best[x..y] = maxim(best[x..(x+y)/2], maxim(best[(x+y)/2 + 1 .. y], max[(x+y)/2 + 1 .. y] - min[x..(x+y)/2])). Acum pentru a raspunde la intrebarile din problema fiecare interval va fi impartit in O(log N) subintervale canonice care apar in arborele de intervale. Apoi printr-o parcurgere asemanatoare celei din rezolvarea anterioara se poate obtine rezultatul pentru fiecare intrebare in O(log N). Solutia va avea complexitatea O(N + M log N).
In urmatorul desen observam structura unui arbore de intervale pentru un sir cu 16 elemente. Daca se pune intrebarea [2, 11] acest interval va fi spart in intervalele [2, 2], [3, 4], [5, 8], [9, 10], [11, 11].

Prezentam procedura de construire a arborelui, implementata in java:

public void build_tree(int index, int low, int high) {
    if (low == high) {
        if (low != 0) aint[index] = new Node(low, high, a[low] - a[low - 1], a[low], a[low]);
        else aint[index] = new Node(low, high, 0, 0, 0);
    }
    else {
        aint[index] = new Node(low, high, -infinity, -infinity, infinity);
        int mid = (low + high) / 2;
        build_tree(2 * index, low, mid);
        build_tree(2 * index + 1, mid + 1, high);
        aint[index].maxS = Math.max(aint[2 * index].maxS,Math.max(aint[2 * index + 1].maxS,aint[2 * index + 1].max - aint[2 * index].min));
        aint[index].max = Math.max(aint[2 * index].max,aint[2 * index + 1].max);
        aint[index].min = Math.min(aint[2 * index].min,aint[2 * index + 1].min);
    }
}

Si procedura care raspunde la intrebari tot in java:

long minPrefix; 
int x, y;
public long queryTree(int index, int low, int high) {
    if (x <= low && high <= y) {
        long maxRet = aint[index].maxS;
        if (minPrefix != infinity) {
            maxRet = Math.max(maxRet, aint[index].max - minPrefix);
        }
        minPrefix = Math.min(minPrefix, aint[index].min);
        return maxRet;
    }
    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));
        else if (x > mid) return queryTree(2 * index + 1, mid + 1, high);
            else return queryTree(2 * index, low, mid);
    }
}

Problema 4 - ACM ICPC NWERC 97, olimpiada online 2000, campion 2001

Se da un sir (a₁, a₂, ..., a_N) format din N numere intregi. Se cere sa se determine subsecventa a[i..j] care are modulul sumei elementelor minim.

Exemplu

Pentru sirul (2, 8, -6, -6, 9, 4, -3), subsecventa este (4, -3), avand suma in modul 1 = |4 - 3|.

Rezolvare

Facem mai intai sirul sumelor partiale. Pentru oricare doua elemente sum[i] si sum[j] ($i != j$) modulul sumei unei subsecvente din sir va fi |sum[i] - sum[j]|. Daca i < j atunci secventa va fi a[i+1..j], iar daca j < i atunci secventa va fi a[j+1 .. i]. Astfel, pentru a gasi subsecventa de modul minim trebuie de fapt sa gasim perechea de indici i si j astfel ca |sum[i] - sum[j]| sa fie minim. Sortand sirul sumelor partiale si luand o pereche de indici i < j, atunci sum[i] < sum[j], iar |sum[j] - sum[i]| = sum[j] - sum[i]. Pentru a gasi perechea (i, j) pentru care i < j si sum[j] - sum[i] este minim, trebuie ca i sa fie egal cu j + 1. Astfel obtinem un algoritm de complexitate O(N log N).

Sa vedem cum merge pe exemplul prezentat:
a:  2 8 -6 -6 9 4 -3
sum: 0 2 10 4 -2 7 11 8
ind: 0 1 2 3 4 5 6 7
In sirul ind vom pastra indicii reali ai sumelor parţiale.

Dupa sortare avem:
sum: $ -2 0 2 4 7 8 10 11$
ind:  $ 4 0 1 4 5 7 2 6$
O secventa de modul 2 ar fi cea reprezentata de sumele 8 si 10 cu indicii 7 si 2. Aceasta secventa este (-6, -6, 9, 4, -3).
Observam ca cea mai mica diferenta intre termeni consecutivi e cea dintre 8 si 7 care au indicii 7 si 5, de unde obtinem ca subsecventa de modul minim este (4, -3).

Problema 5 - USACO

Se da un sir (a₁, a₂, ..., a_N) format din N (1 <= N <= 100 000) numere intregi ($1 <= a_i <= 2 000$). Se cere sa se determine subsecventa a[i..i + K - 1] cu media aritmetica a elementelor maxima ( K >= F, 1 <= F <= N).

Exemplu

Pentru sirul (6, 4, 2, 10, 3, 8, 5, 9, 4, 1) si F = 6 soluţia optima este (10, 3, 8, 5, 9, 4), cu media 6.5.

Rezolvare

Fie X un numar real. Daca obtinem sirul b prin transformarea b_i = a_i - X, atunci toate subsecventele sirului b vor avea valoarea mediei elementelor lor cu X mai mica decat valoarea subsecventelor corespunzatoare din sirul a. Daca subsecventa de suma maxima din b are valoarea mai mare ca 0, atunci si media ei va fi mai mare ca 0. Rezulta astfel ca si media subsecventei corespunzatoare din sirul a va fi mai mare decat X, deci media maxima a unei subsecvente din a va fi mai mare ca X. Cand subsecventa de suma maxima din sirul b are media mai mica decat zero, atunci orice subsecventa din sirul a va avea media mai mica decat X. Iar in cazul in care subsecventa de suma maxima a sirului b are valoarea egala cu zero, atunci subsecventa de medie maxima a sirului a are media X. Astfel putem face o cautare binara pentru a determina valoarea X a mediei maxime. Ne mai ramane sa determinam un algoritm eficient pentru gasirea subsecventei de suma maxima de lungime cel putin F.
O asemenea solutie este usor de facut urmarind una din ideile din prima problema: fie best[i] subsecventa de suma maxima care se termina in a[i]. Evident best[i] = max(a[i], best[i - 1] + a[i]). Acum secventa de suma maxima ce se termina in a[i] de lungime cel putin F se gaseste ca a[i] + a[i - 1] + .. + a[i - F + 2] + best[i - F + 1]. Aceasta relatie poate fi calculata in O(1) daca ne folosim de trucul sumelor partiale.
Astfel obtinem o solutie de complexitate O(N log C), unde C e valoarea maxima a lui $a_i.