Scrie aici despre probleme-cu-secvente

h1. Probleme cu secvente
 
(Categoria _Diverse_, autor _Cosmin Negruseri_)
 
(toc){width: 25em}*{text-align:center} *Cuprins*
* 'Introducere ':probleme-cu-secvente#intro
* 'Problema 1 ( _Subsecventa de suma maxima_ ) ':probleme-cu-secvente#prob1
 
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.
 
h2(#prob1). Problema 1 ( _Subsecventa de suma maxima_ )
 
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.
 
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)$.
 
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)$.
 
== 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;
   }
}
==
 
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^)$).
 
== code(cpp) |
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.
 
== 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.
 
== 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 ));
}
==
 
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 ];
}
==
 
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.
 
== code(cpp) |
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;
}
==