[C++, programare dinamică] Problema subsecvenței de sumă maximă

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Considerăm un număr natural N și un vector A cu N elemente numere întregi. O subsecvență [st, dr] a vectorului A reprezintă suma tuturor elementelor acelei subsecvențe. Se cere determinarea unei subsecvențe de sumă maximă.

Datele de intrare se citesc din fișierul subsecv.in, iar suma maximă se va afișa în fișierul subsecv.out.

Exemplu:

subsecv.in	subsecv.out
6 1 -3 4 5 -1 3 -8 -9 1	11

Vom prezenta trei metode de rezolvare, începând de la o metodă trivială și sfârșind cu metoda optimă de rezolvare, care constă într-o singură parcurgere a vectorului.

In implementările oferite ca model vom prezenta doar o funcție subsecvi(A, N) care primește ca parametri vectorul A respectiv dimensiunea acestuia și returnează suma maximă a unei subsecvențe. Considerăm citirea și afișarea ca fiind cunoscute.


Prima metodă constă în verificarea tuturor subsecvențelor vectorului de intrare A. Pentru fiecare subsecvență [st, dr] vom parcurge elementele A[st], A[st + 1], ..., A[dr] și vom face suma acestora. Dacă această sumă este mai mare decât maximul curent (inițializat la început cu o valoare foarte mică: -infinit), actualizăm maximul curent. Complexitatea acestei metode este O(N³), deoarece există O(N²) subsecvențe și fiecare dintre acestea trebuie parcursă pentru a-i afla suma.


Putem implementa această metodă în felul următor:

A doua metodă de rezolvare are complexitatea O(N²) și este o simplă optimizare a primei metode. Vom încerca să eliminăm parcurgerea prin care facem suma subsecvenței [st, dr], sau, altfel spus, vom încerca să calculăm suma fiecărei subsecvențe pe măsură ce acestea sunt generate și nu pentru fiecare în parte printr-o parcurgere. Să presupunem că știm care este suma temp a unei subsecvențe [st, dr]. Atunci suma subsecvenței [st, dr + 1] va fi temp + A[dr + 1]. Vom inițializa așadar temp cu 0 pentru fiecare st, iar apoi vom aduna, pentru fiecare dr, pe A[dr] la temp și îl vom compara pe temp cu max:

Această implementare este deja relativ eficientă pentru vectori cu un număr de elemente de până la ordinul miilor, spre deosebire de prima implementare care este aplicabilă doar pentru un număr de elemente de ordinul sutelor. Putem obține însă o rezolvare și mai eficientă, care funcționează rapid pe vectori cu sute de mii sau chiar milioane de elemente.


Cea de-a treia metodă folosește paradigma programării dinamice pentru a obține o rezolvare în O(N). Fie S[i] = suma maximă a unei subsecvențe care se termină cu elementul i. Să presupunem că, pentru un anume 1 ≤ k < N, cunoaștem valoarea lui S[k]. Ne interesează să-l obținem pe S[k + 1] din S[k]. Observăm că avem două posibilități:

1. Adăugăm elementul k + 1 la sfârșitul subsecvenței de sumă maximă care se termină cu elementul k, obținând o subsecvență de sumă A[k + 1] + S[k],

2. Ignorăm subsecvența de sumă maximă care se termină cu elementul k și considerăm subsecvența formată doar din elementul k + 1, aceasta având suma A[k + 1].


Evident vom alege maximul sumelor aferente celor două cazuri. Așadar, obținem următoarea formulă de recurență:

S[k + 1] = max(A[k + 1] + S[k], A[k + 1]).

Să evidențiem modul de execuție al algoritmului pe exemplul dat. Inițial avem:

i	1	2	3	4	5	6	7	8	9	10
A[i]	-6	1	-3	4	5	-1	3	-8	-9	1
S[i]	-6

Pentru S[2] luăm maximul dintre S[1] + A[2] și A[2].
S[1] + A[2] = -1, iar A[2] = 1. Maximul este așadar A[2] = 1:

i	1	2	3	4	5	6	7	8	9	10
A[i]	-6	1	-3	4	5	-1	3	-8	-9	1
S[i]	-6	1

Se observă ușor că subsecvența de sumă maximă care se termină pe poziția 2 are suma 1 (cealaltă posibilitate fiind doar subsecvența [1, 2] care are suma -5), deci se respectă definiția lui S.

La sfârșit, vectorul S este următorul. Se poate verifica, folosind eventual implementările precedente, că acesta este corect calculat.

i	1	2	3	4	5	6	7	8	9	10
A[i]	-6	1	-3	4	5	-1	3	-8	-9	1
S[i]	-6	1	-2	4	9	8	11	3	-6	1

[ n.e. In loc de max = -inf trebuia max = A[1]. ]

Exerciții:

a) Modificați implementările date pentru a afișa și pozițiile de început și de sfârșit a unei subsecvențe de sumă maximă.

b) Se cere o subsecvență de produs maxim, iar numerele sunt reale. Rezolvați problema atât pentru numere strict pozitive cât și pentru numere nenule (dar care pot fi negative).

c) Se dă o matrice și se cere determinarea unui dreptunghi de sumă maximă. Ultimul algoritm prezentat poate fi extins pentru rezolvarea problemei în O(N³). Cum?