Probleme cu secvente

(Categoria Diverse, autor Cosmin Negruseri)

• Cuprins
• Introducere
• Problema 1 ( Subsecventa de suma maxima )
• Problema 2 (Maximum Sum) - 104 acm.uva.es
• Problema 3 (Interogare) - Bursele Agora 2005/2006 Runda 1

Introducere

Acest articol prezinta o serie de probleme inrudite cu problema subsecventei de suma maxima, insotite de rezolvari eficiente. Problemele prezentate pot aparea oricand ca subprobleme in concursurile de programare, studierea lor marind in mod util bagajul de cunostinte al unui elev pasionat de algoritmica.

Problema 1 ( Subsecventa de suma maxima )

Se da un şir A = ( a₁, a₂, ... , a_N) de numere intregi. Sa se determine o subsecventa ( a_i, a_i+1, ... , a_j) care sa aiba suma maxima.

Exemplu

Pentru secventa de numere (-1, 2, 3, -4, -2, 2, 1, -3, -2, -3, -4, 9, -2, 1, 7, 8, -19, -7, 2, 4, 3), o subsecventa de suma maxima este (9, -2, 1, 7, 8).

Rezolvare

Prima rezolvare care ne vine in minte este: pentru orice subsecventa sa ii determinam suma, iar apoi sa determinam maximul acestor sume. Aceasta solutie are complexitatea O(N^3).

bestSum = -infinit;
for (i = 1; i <= N; i++) {
   for (j = i; j <= N; j++) {
         sum = 0;
         for (k = i; k <= j; k++) sum += a[ k ];
         if (bestSum < sum) bestSum = sum;         
   }
}

Este evident ca se calculeaza anumite sume partiale de mai multe ori. Pentru a reduce complexitatea la O(N²) este necesar sa observam ca suma subsecventei a[ i..j ] este egala cu suma subsecventei a[ i..j-1 ], la care se aduna a[ j ].
Alta idee este de a pastra intr-un sir sum[ i ] - suma elementelor din subsecventa a[ 1..i ]. Pentru a determina suma elementelor din subsecventa a[ i..j ] putem face calculul sum[ i ] - sum[ j-1 ] (complexitate O(N²)).

sum[ 0 ] = 0;
for (i = 1; i <= N; i++) sum[ i ] = a[ i ] + sum[ i - 1 ];
bestSum = -infinit;
for (i = 1; i <= N; i++) {
   for (j = i; j <= N; j++) {
         if (bestSum < sum[ i ] – sum[ j - 1 ]) bestSum = sum[ i ] - sum[ j - 1 ];
   }
}

Putem sa rafinam aceasta idee calculand pentru fiecare indice i numarul best[ i ] ( subsecventa de suma maxima ce are capatul drept in i ). Este usor de observat ca best[ i ] = max( sum[ i ] - sum[ j-1 ] ), unde j ia valori de la 1 la i. Relatia anterioara este echivalenta cu best[ i ] = sum[ i ] – min( sum[ j-1 ] ). Obtinem astfel un algoritm liniar care ne determina subsecventa de suma maxima.

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

Putem incerca o abordare bazata pe paradigma divide et impera. La fiecare pas impartim sirul in jumatate si aflam subsecventele de suma maxima din cele doua jumatati. Dupa aceea trebuie sa gasim subsecventa de suma maxima care are cate un capat in fiecare din cele doua jumatati ale sirului. Gasim aceasta secventa prin alipirea sufixului de suma maxima a primei jumatati cu prefixul de suma maxima 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 = -infinity; 
     maxPre = -infinity;
     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 bazata pe paradigma programarii dinamice ar fi sa folosim un sir best[ i ], reprezentand suma maxima a unei subsecvente ce se termina in a[ i ]. Se poate demonstra prin inductie ca sirul best satisface urmatoarea recurenta best[ i ] = max( a[ i ], best[ i-1 ] + a[ i ] ).

bestSum = a[ 1 ];
for (i = 1; i <= N; i++) {
     best[ i ] = a[ i ];
     if (best[ i ] < best[ i-1 ] + a[ i ]) best[ i ] = best[ i-1 ] + a[ i ];
     if (bestSum < best[ i ]) bestSum = best[ i ];
}

Alta idee ar fi sa partitionam sirul in subsecvente, astfel incat fiecare dintre acestea sa aiba ambele capete cat mai mici posibile si suma elementelor subsecventei sa fie negativa. Pe exemplul data avem [-1], [2, 3, -4, -2], [2, 1, -3, -2], [-3], [-4], [9, -2, 1, 7, 8, -19, -7], [2, 4, 3]. Este evident ca o subsecventa de suma maxima va avea primul capat la inceputul unei astfel de subsecvente. Acest lucru se explica prin faptul ca in caz contrar secventa poate fi marita in stanga ( orice secventa din cele alese pentru partitionare are toate prefixele de suma pozitiva, in afara de prefixul ce reprezinta intreaga subsecventa ). De asemenea, orice subsecventa de suma maxima nu va contine elemente din alta parte a partitiei, pentru ca daca subsecventa se intinde pe mai multe parti, atunci putem elimina prefixul subsecventei care reprezinta o parte a partitiei, acea parte avand suma negativa.

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) - 104 acm.uva.es

Se da o matrice de dimensiuni NxN cu elemente intregi. Se cere determinarea unei submatrici a carei elemente au suma maxima.

Exemplu

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

Rezolvare

Putem folosi trucul construirii sumelor partiale prezentat in rezolvarea anterioara, pentru cazul 2D. Pastram in sum[i][j] suma tuturor elementelor a[i₁][j₁] cu proprietatea ca 1 <= i₁ <= i, si 1 <= j₁ <= j. Putem calcula sumele prin metoda programarii 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 colturile (i₁, j₁), (i₂, j₂), unde i₁ <= i₂ si j₁ <= j₂ este suficient sa 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 in timp constant, deci rezolvarea are ordinul de complexitate O(N⁴).
O alta idee ar fi ca pentru fiecare pereche (i₁, i₂) fixate sa determinam perechea optima (j₁, j₂). Daca avem liniile i₁ si i₂ fixate atunci problema se transforma din una bidimensionala in una unidimensionala. Astfel pentru fiecare coloana j vom considera b[j] ca suma a elementelor a[i][j] cu proprietatea ca i₁ <= i <= i₂. In exemplul nostru daca i₁ = 2 si i₂ = 3, atunci avem b₁ = 9 + (-4), b₂ = 2 + 1, b₃ = (-6) + (-4) si b₄ = 2 + 1. Pentru a rezolva problema unidimensionala folosim unul din algoritmii liniari prezentati mai sus, astfel obtinandu-se un algoritm de complexitate totala O(N³). Acest truc de a fixa doua linii pentru a transforma problema in una unidimensionala este util in multe probleme pe matrice sau cu puncte in plan.
Cel mai bun algoritm cunoscut pentru aceasta problema 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).