• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Subsecventa de suma maxima

3
  • Publicat de Coss
  • în C/C++
  • — 4 ian., 2010 at 12:37 am

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

Etichete: algoritmi subsecventealgoritmicaC++subsecventa de suma maximaTehnic

— Albulescu Cosmina a scris 223 articole

Nu există o descriere a autorului.

  • Articolul anterior Nokia N900 – review
  • Articolul următor Google Pack pentru Windows 7

3 Comentarii

  1. Andrei Misarca spune:
    ianuarie 11, 2010 la 9:28 pm

    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

  2. Olariu Ciprian spune:
    septembrie 26, 2010 la 3:35 pm

    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)…

  3. Andrei Avadanei spune:
    septembrie 26, 2010 la 8:02 pm

    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. 🙂


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • ianuarie 2023
    L Ma Mi J V S D
     1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Subsecventa de suma maxima
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons