h1. Probleme cu secvente
h1. Probleme cu secvenţe
(Categoria _Diverse_, autor _Cosmin Negruseri_)
(Categoria _Diverse_, autor _Cosmin Negruşeri_)
(toc){width: 30em}*{text-align:center} *Cuprins*
* 'Introducere ':probleme-cu-secvente#intro
* 'Problema 1 ( _Subsecventa de suma maxima_ ) ':probleme-cu-secvente#prob1
* 'Problema 1 ( _Subsecvenţa de sumă maximă_ ) ':probleme-cu-secvente#prob1
* 'Problema 2 ({_Maximum Sum_}) - 104 acm.uva.es ':probleme-cu-secvente#prob2
* 'Problema 3 ({_Interogare_}) - Bursele Agora 2005/2006 Runda 1 ':probleme-cu-secvente#prob3
h2(#intro). 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.
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 ( _Subsecventa de suma maxima_ )
h2(#prob1). Problema 1 ( _Subsecvenţa de sumă maximă_ )
Se da un şir $A$ = ( $a{~1~}$, $a{~2~}$, ... , $a{~N~}$) de numere intregi. Sa se determine o subsecventa ( $a{~i~}$, $a{~i+1~}$, ... , $a{~j~}$) care sa aiba suma maxima.
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ă.
h4. 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)$.
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)$.
h3. 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)$.
Prima rezolvare care ne vine în minte are complexitatea $O(N^3^)$ ş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.
== code(cpp) |
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;
}
}
==
Putem reduce complexitatea la $O(N^2^)$ ţ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]$.
Este evident ca se calculeaza anumite sume partiale de mai multe ori. Pentru a reduce complexitatea la $O(N^2^)$ 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^2^)$).
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ă.
== code(cpp) |
sum[ 0 ] = 0;
for (i = 1; i <= N; i++) sum[ i ] = a[ i ] + sum[ i - 1 ];
bestSum = -infinit;
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++) {
for (j = i; j <= N; j++) {
if (bestSum < sum[ i ] – sum[ j - 1 ]) bestSum = sum[ i ] - sum[ j - 1 ];
}
best[i] = sum[i] - min;
if (min > sum[i]) min = sum[i];
if (bestSum < best[i]) bestSum = best[i];
}
==
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.
== code(cpp) |
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.
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.
== code(cpp) |
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 ));
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 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 ] )$.
== code(cpp) |
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 ];
}
==
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ă.
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.
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ă.
== code(cpp) |
sum = -infinit; bestSum = -infinit;
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;
sum += a[i];
if (sum < 0) {
sum = 0;
continue;
} else
if (sum >= bestSum) bestSum = sum;
}
==
