Subsecvența de sumă maximă în C++

Subsecvența de sumă maximă în C++

Subsecvența de sumă maximă este o problemă clasică de programare dinamică, întâlnită adesea la concursurile de informatică, într-o formă sau alta. În acest articol voi prezenta o soluție în O(nlogn)O(n \log n) bazată pe divide et impera, și două soluții în O(n)O(n) dintre care una folosește programare dinamică. De asemenea, voi arăta și cum putem rezolva eficient extinderea problemei la două dimensiuni.

Enunț

Se dă un vector vv cu nn elemente întregi, indexate de la 11 Să se determine suma maximă a elementelor unei subsecvențe a vectorului dat, precum și o astfel de subsecvență. O subsecvență a vectorului vv reprezintă o succesiune de elemente de forma v[i],v[i+1],,v[j]\langle v[i], v[i+1], \ldots, v[j] \rangle cu 1ijn1 \le i \le j \le n

Putem la fel de bine ca în loc de subsecvență să-i spunem doar secvență, dar având în vedere că în literatura de specialitate problema se numește Maximum Sum Subsequence, am păstrat termenul de subsecvență. Apropo, cuvântul este subsequence deoarece sequence este șirul de numere.

De exemplu, pentru v=5,1,2,4,2,5,7v = \langle 5, -1, 2, 4, -2, -5, 7 \rangle o subsecvență de sumă maximă este 5,1,2,4\langle 5, -1, 2, 4 \rangle suma elementelor acesteia fiind 1010 Soluția nu este neapărat unică. Pentru acest exemplu, o altă subsecvență de sumă maximă este 5,1,2,4,2,5,7\langle 5, -1, 2, 4, -2, -5, 7 \rangle care se întâmplă să fie întreg vectorul.

Soluții naive

O soluție imediată este să calculăm suma fiecărei subsecvențe în parte și să reținem pe parcurs suma maximă. Numărul de subsecvențe ale unui vector cu nn elemente este n(n+1)/2n(n+1)/2 Putem demonstra asta foarte ușor, observând că numărul de subsecvențe care se termină pe poziția jj (1jn\htmlClass{katexified}{(} 1 \le j \le n este jj căci începutul poate lua orice valoare din mulțimea {1,2,,j}\{1, 2, \ldots, j\} Având în vedere că fiecărei subsecvențe îi calculăm suma elementelor în timp liniar, complexitatea finală a algoritmului devine O(n3)O(n^3)

int ans = -2e9;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++) {
int sum = 0;
for (int k = i; k <= j; k++)
sum += v[k];
ans = max(ans, sum);
}

Putem optimiza această soluție calculând suma elementelor unei subsecvențe cu capătul din stânga fixat în ii pe măsură ce ne extindem în dreapta cu capătul jj Astfel, obținem un algoritm în complexitate O(n2)O(n^2) ceea ce, în continuare, nu este mulțumitor.

int ans = -2e9;
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = i; j <= n; j++) {
sum += v[j];
ans = max(ans, sum);
}
}

Soluție în O(nlogn)O(n \log n) – Divide et impera

Soluția în O(nlogn)O(n \log n) folosește paradigma divide et impera, fiind un algoritm ce ilustrează foarte bine principiul acestei metode de programare. Chiar dacă soluția nu este optimă, nu înseamnă că nu e utilă. Combinată cu un arbore de intervale, această metodă poate fi folosită pentru a rezolva probleme în care trebuie să găsim eficient subsecvența de sumă maximă pe anumite intervale dintr-un vector.

Iată deci cum funcționează algoritmul:

  • Divide: Împărțim vectorul în două părți aproximativ egale.

  • Stăpânește: Calculăm recursiv subsecvența de sumă maximă din fiecare jumătate.

  • Combină: Subsecvența de sumă maximă din întreg vectorul se poate afla fie în prima jumătate (j[n/2]\htmlClass{katexified}{(} j \le [n/2] fie în a doua jumătate (i>[n/2]\htmlClass{katexified}{(} i \gt [n/2] fie începe în prima jumătate și se termină în a doua (1i[n/2]<jn\htmlClass{katexified}{(} 1 \le i \le [n/2] \lt j \le n Valorile corespunzătoare primelor două cazuri au fost calculate deja la pasul precedent. Pentru a rezolva al treilea caz, procedăm astfel: Îl fixăm pe ii în [n/2][n/2] și pe jj în [n/2]+1[n/2]+1 Îl decrementăm pe ii până la 11 ținând pe parcurs suma maximă a unei secvențe care începe în ii și se termină în [n/2][n/2] Procedăm similar și cu jj Adunând cele două sume, obținem rezultatul pentru al treilea caz. Nu ne mai rămâne decât să calculăm maximul dintre cele trei valori.

Desigur, cazul de bază este acela când secvența curentă are un singur element. În acest caz, returnăm respectiva valoare. Iată mai jos o implementare elegantă a acestei soluții. Funcția dei\mathrm{dei} se apelează inițial cu parametrii 11 și nn

int dei(int l, int r) {
if (l == r)
return v[l];
int bstL = -2e9, sumL = 0;
for (int i = (l + r) / 2; i >= l; i--)
bstL = max(bstL, sumL += v[i]);
int bstR = -2e9, sumR = 0;
for (int j = (l + r) / 2 + 1; j <= r; j++)
bstR = max(bstR, sumR += v[j]);
return max(bstL + bstR, max(
dei(l, (l + r) / 2),
dei((l + r) / 2 + 1, r)
));
}

Complexitate

La fel ca majoritatea algoritmilor divide et impera, avem de a face cu o complexitate de ordinul O(nlogn)O(n \log n) lucru care poate fi observat ușor din arborele de execuție al funcției dei\mathrm{dei}

Arborele de execuție

Pe fiecare nivel, suma lungimilor secvențelor corespunzătoare apelurilor este nn Cum pentru fiecare apel dei(l,r)\mathrm{dei}(l, r) în etapa combină efectuăm rl+1r - l + 1 pași, complexitatea totală pe un nivel este O(n)O(n) În plus, adâncimea arborelui este aproximativ [log2n][\log_2 n] iar de aici putem trage concluzia că algoritmul nostru are complexitatea O(nlogn)O(n \log n)

Soluție în O(n)O(n) – Sume parțiale

Soluția următoare folosește doar conceptul de sume parțiale, și dintr-un motiv sau altul este destul de nepopulară. Probabil e mai șmecher să folosești programare dinamică Să notăm cu sis_i (0in\htmlClass{katexified}{(} 0 \le i \le n a iia sumă parțială a lui vv Avem si=v[1]+v[2]++v[i]s_i = v[1] + v[2] + \cdots + v[i] pentru i>0i \gt 0 iar s0=0s_0 = 0 Astfel, putem afirma că suma subsecvenței v[i..j]v[i..j] este egală cu sjsi1s_j - s_{i-1} Deci, suma maximă a unei subsecvențe ce se termină în jj se obține scăzând din sjs_j cea mai mică sumă parțială si1s_{i-1} cu 1ij1 \le i \le j

Așadar, ideea este să parcurgem vectorul menținând suma prefixului curent (ps\htmlClass{katexified}{(} ps cât și suma parțială minimă din acest prefix (mn\htmlClass{katexified}{(} mn La fiecare pas calculăm suma maximă a unei subsecvențe ce se termină pe poziția curentă și actualizăm maximul global dacă e cazul. Complexitatea este în mod evident O(n)O(n) Iată implementarea acestei metode:

int ans = -2e9, ps = 0, mn = 0;
for (int i = 1; i <= n; i++) {
ps += v[i];
ans = max(ans, ps - mn);
mn = min(mn, ps);
}

Soluție în O(n)O(n) – Programare dinamică

Această soluție folosește metoda programării dinamice și se numește Algoritmul lui Kadane. Dacă nu sunteți familiarizați cu programarea dinamică, nu este o problemă, aceasta fiind poate cea mai simplă formă posibilă de dinamică. Din nou, ideea este să calculăm pentru fiecare poziție ii din vector suma maximă a unei subsecvențe ce se termină în ii Vom nota această valoare cu dp[i]\mathrm{dp}[i] Recurența este următoarea:

dp[i]={max(dp[i1]+v[i],v[i])pentru i10pentru i=0\mathrm{dp}[i] = \begin{cases} \max(\mathrm{dp}[i - 1] + v[i], v[i]) & \text{pentru } i \ge 1\\ 0 & \text{pentru } i = 0 \end{cases}

Explicația este simplă: Răspunsul pentru ii poate fi obținut din cel pentru i1i - 1 adăugând elementul v[i]v[i] însă dp[i1]\mathrm{dp}[i - 1] s-ar putea să fie negativ, caz în care este mai bine să considerăm doar elementul curent.

vector<int> dp(n + 1);
int ans = -2e9;
for (int i = 1; i <= n; i++) {
dp[i] = max(dp[i - 1], 0) + v[i];
ans = max(ans, dp[i]);
}

Putem reduce complexitatea în spațiu de la O(n)O(n) la O(1)O(1) renunțând la vectorul dp\mathrm{dp} și ținând în schimb o singură variabilă sumsum egală cu valoarea stării precedente (dp[i1]\htmlClass{katexified}{(} \mathrm{dp}[i - 1]

int ans = -2e9, sum = 0;
for (int i = 1; i <= n; i++) {
sum = max(sum, 0) + v[i];
ans = max(ans, sum);
}

Iar dacă tot am precizat în enunț că trebuie să determinăm și o subsecvență de sumă maximă, hai s-o facem măcar de data asta! Reținem în ll și rr capetele răspunsului, iar în ii capătul din stânga al subsecvenței curente de sumă maximă.

int ans = -2e9, l = 0, r = 0;
int sum = 0, i = 0;
for (int j = 1; j <= n; j++) {
if (sum > 0)
sum += v[j];
else {
i = j;
sum = v[j];
}
if (sum > ans) {
ans = sum;
l = i;
r = j;
}
}

Extinderea la 2D

Enunțul problemei noastre se poate extinde la două dimensiuni astfel: Dându-se o matrice aa cu mm linii și nn coloane, să se determine suma maximă a unei submatrice a lui aa De fapt chiar de aici a pornit totul: Problema inițială era cea 2D, dar pentru că nu se găseau soluții prea bune, s-a propus studiul problemei 1D pentru a înțelege mai bine mecanismul unui algoritm optim. Puteți citi aici istoricul problemei; mi se pare destul de interesant.

Soluția cea mai ineficientă are complexitatea O(n6)O(n^6) și presupune calcularea sumei elementelor din fiecare submatrice posibilă. O putem reduce la O(n4)O(n^4) precalculând sumele parțiale 2D în O(n2)O(n^2) Dar se poate și mai bine, generalizând una dintre soluțiile liniare pentru problema unidimensională. O voi alege pe cea cu programare dinamică.

Ideea este să ne fixăm două linii ii și jj ale matricei, și să reducem problema găsirii submatricei de sumă maximă care începe pe linia ii și se termină pe linia jj la problema găsirii subsecvenței de sumă maximă într-un vector. În acest sens, vom crea un vector vv de lungime nn cu proprietatea v[k]=a[i][k]+a[i+1][k]++a[j][k]v[k] = a[i][k] + a[i+1][k] + \cdots + a[j][k] Aplicând Algoritmul lui Kadane pentru fiecare pereche de linii (i,j)(i, j) cu 1ijm1 \le i \le j \le m și reținând maximul, am rezolvat problema în O(n3)O(n^3) Mă rog, dacă e să fim riguroși, este O(m2n)O(m^2 n) Avem O(m2)O(m^2) de la numărul de perechi și O(n)O(n) de la algoritmul liniar aplicat pentru fiecare astfel de pereche. Și de la actualizarea lui vv care este creat (sau inițializat cu 00 pentru fiecare ii

int ans = -2e9;
for (int i = 1; i <= m; i++) {
vector<int> v(n + 1);
for (int j = i; j <= m; j++) {
for (int k = 1; k <= n; k++)
v[k] += a[j][k];
int sum = 0;
for (int k = 1; k <= n; k++) {
sum = max(sum, 0) + v[k];
ans = max(ans, sum);
}
}
}

Iată un exemplu pentru a vizualiza mai bine algoritmul:

a=(1214208342138101341176)a = \begin{pmatrix} 1 & 2 & -1 & -4 & -20\\ -8 & \textcolor{orangered}{-3} & \textcolor{orangered}{4} & \textcolor{orangered}{2} & 1\\ 3 & \textcolor{orangered}{8} & \textcolor{orangered}{10} & \textcolor{orangered}{1} & 3\\ -4 & \textcolor{orangered}{-1} & \textcolor{orangered}{1} & \textcolor{orangered}{7} & -6 \end{pmatrix}

Submatricea de sumă maximă este cea colorată cu roșu, și are suma elementelor 2929 Vectorul vv asociat perechii de linii (2,4)(2, 4) este 9,4,15,10,2\langle -9, \textcolor{orangered}{4}, \textcolor{orangered}{15}, \textcolor{orangered}{10}, -2 \rangle Subsecvența de sumă maximă a acestuia este 4,15,10\langle 4, 15, 10 \rangle are suma 2929 și îi corespunde submatricei cu colțurile în (2,2)(2, 2) și (4,4)(4, 4) care este chiar răspunsul.

Probleme recomandate

Dacă aveți vreo întrebare despre problema subsecvenței de sumă maximă, nu ezitați să o adresați mai jos, într-un comentariu

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii