Subsecventa de suma maxima
3Urmatorul articol contine probleme, implementari si explicatii ale algoritmilor folositi. Voi incerca sa prezint algoritmul de aflare a subsecventei cu suma maxima a unui vector si in acelasi tip sa dau exemple practice.
Fie dat un vector dat V, de lungime N (V[1], V[2], … , V[N]). Sa se determine o subsecventa a vectorului, in care suma sa fie maxima.
N = 7
V : (5 -6 3 4 -2 3 -3)
In vectorul V subsecventa de suma maxima incepe de pe pozitia 3 si se termina pe pozitia 6, suma fiind 8. Asadar elementele subsecventei sunt 3 4 -2 3.
Solutiile la care ne putem gandi sunt mai mult sau mai putin eficiente. Am putea sa fixam indicii de inceput si de sfarsit si sa calculam sumele, determinand maximul lor.
Implementarea este aceasta:
#include <stdio.h> int v[1000]; int n, i, j, k; int sum, S, st, dr; int main() { FILE *f = fopen ("secv.in","r"); fscanf (f,"%d", &n); for (i=1; i<=n; ++i) fscanf (f,"%d", &v[i]); fclose(f); for (i=1; i<=n; ++i) { for (j=n; j>=1; --j) { sum = 0; for (k=i; k<=j; ++k) sum += v[k]; if (sum > S) { S = sum; st = i; dr = j; } } } printf ("Suma maxima = %d\n", S); printf ("Pozitia de inceput a secventei %d , pozitia se sfarsit a secventei %d", st, dr); return 0; }
Complexitatea este O(N^3), iar pentru valori mari ale lui N poate depasi cu mult timpul de executie.
Vom incerca o abordare mai interesanta, folosind Divide & Impera. Vom injumatati vectorul si calculam la fiecare pas subsecventa de suma maxima din cele doua jumatati.
Apoi va trebui sa aflam subsecventa de suma maxima care un capat in fiecare jumatate. Ca sa realizam acest lucru vom lipi sufixul de suma maxima al primei jumatati cu prefixul de suma maxima al celei de-a doua.
/* Implementare preluata de pe infoarena */ 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 = -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 solutie optima, de complexitate O(N) este urmatoarea:
#include <stdio.h> int n; int nr, i; int st, poz, sol, SMax, dr; int main() { FILE *f = fopen ("secv.in","r"); fscanf (f,"%d", &n); sol = -0x3f3f3f3f; /* sol este -Infinit */ for (i=1;i<=n;++i) { fscanf (f,"%d", &nr); if (SMax < 0) { SMax = nr; poz = i; } else SMax += nr; if (SMax > sol) { sol = SMax; st = poz; dr = i; } } fclose(f); printf ("Suma maxima = %d\n", sol); printf ("Pozitia de inceput a secventei %d , pozitia se sfarsit a secventei %d", st, dr); return 0; }
Dupa cum ati observat, nu am mai retinut numerele intr-un vector si le-am citit direct. La fiecare pas am verificat ‘starea’ sumei curente. In caz de nulitate am atribuit sumei valaorea citita,
si am setat pozitia de inceput, iar in situatia de natura opusa am adaugat doar numarul curent. La fiecare pas comparam suma curenta cu suma maxima (pe care am reitnut-o in variabila sol)
si resetam pozitiile.
- Probleme care lucreaza cu secvente:
Sursele au fost compilate in MinGW Developer Studio.
Limbaj de programare : C
SequenceQuery nu cred ca este neaparat o problema in care in primul rand se lucreaza cu secvenÈ›e, ci mai degraba cu arbori de intervale 🙂 Anyway, frumos prezentate soluÈ›iile pentru problema subsecvenÈ›ei de suma maxima
Imi dau seama ca acest articol a fost scris prin ianuarie,dar am o mica observatie de facut…
la aceasta problema daca se introduc in vector NUMAI numere negative,atunci nu mai returneaza o valoare corecta…
Corect ar fi sa se afiseze in acest caz cel mai mare dintre numerele din vector(toate fiind negative)…
Salut Ciprian si bun venit pe blog.
Data nu are o relevanta aici, ai foarte mare dreptate. Doar ca aici e doar un concept prezentat pentru o problema clasica. Tu o vei adapta pentru problema care o ai in fata. Evident, a fost o omitere din partea celui care a redactat-o, insa e foarte bine ca ai subliniat acest lucru. 🙂