Subsecventa de suma maxima

Urmatorul 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:

Perle 2
SequenceQuery

Sursele au fost compilate in MinGW Developer Studio.
Limbaj de programare : C