Secvenţa de sumă maximă

Apărut la 8.10.2017 în Algoritmi   |   autor: Dan Pracsiu 1 comentarii

Problema: Se consideră un şir a₁, a₂, ..., a_n de numere întregi. Să se determine o secvenţă din acest şir care are suma maximă. Prin secvenţă se înţelege o succesiune de unul sau mai mulţi termeni din şir aflaţi pe poziţii consecutive. De exemplu, pentru şirul 2, -5, 6, -2, -3, 4, 7, -6, 1, suma maximă a unei secvenţe este 12 (este vorba de secvenţa 6, -2, -3, 4, 7).

Soluţia 1, de complexitate O(n²), se bazează pe calculul în prealabil a vectorului sumelor parţiale sp, în care sp[i] = a₁ + a₂ + ... + a_i. Se parcurge apoi şirul a cu doi indici i şi j, i <= j, calculându-se suma a_i + a_i+1 + ... + a_j = sp[j] - sp[i-1] şi actualizând, dacă este cazul, valoarea maximă. Algoritmul este următorul:

// date de intrare: vectorul a de lungime n
// date intermediare: vectorul sp de lungime n
// date de iesire: smax - suma maxima a unei secvente din a

sp[0] ← 0
sp[1] ← a[1]
for i ← 2, n do
  sp[i] ← sp[i-1] + a[i]
endfor

smax ← a[1]

for i ← 1, n do
  for j ← i, n do
    x ← sp[j] - sp[i-1]
    if (x > smax) smax ← x
    endif
  endfor
endfor
write 'suma maxima este ', smax

Soluţia 2, complexitate O(n). Se parcurge o singură dată şirul. Pe lângă smax, care memorează valoarea maximă a unei secvenţe, se mai păstrează o valoare s a unei secvenţe curente pozitive. La ce foloseşte s? Practic se va împărţi şirul în subsecvenţe cât mai lungi de sume pozitive sau negative. Cele pozitive sunt candidate la suma maximă, cele negative nu. De exemplu, dacă şirul a este 2, -5, 3, 4, -1, 6, -7, atunci secvenţa formată din primele două numere (adică 2, -5) este de sumă negativă. Ea nu va putea contribui la suma maximă globală, deci o eliminăm. În schimb, în secvenţa 3, 4, -1 suma s este 6 şi chiar dacă am efectuat o scădere cu 1, continuăm să o "prelungim" cu valoarea 6. Am obţinut acum şi suma maximă 12 a unei secvenţe: 3, 4, -1, 6. Ideea va fi ca la fiecare pas i să adunăm la s valoarea curentă a_i, actualizăm dacă este cazul suma maximă şi, dacă s a devenit negativă, atunci o reiniţializăm cu 0.

Algoritmul este următorul:

// date de intrare: vectorul a de lungime n
// date de iesire: smax - suma maxima a unei secvente din a
smax ← a[1]
s ← a[1]
if (s < 0) s ← 0
endif

for i ← 2, n do
  s ← s + a[i]
  if (s > smax) smax ← s
  endif
  if (s < 0) s = 0
endfor
write 'suma maxima este ', smax

Acest algoritm este funcţional şi dacă întreaga secvenţă este formată doar din valori negative. Suma maximă va fi formată dintr-un singur număr, anume cel mai mare dintre ele. Vă las ca exerciţiu modificarea algoritmului astfel încât să se afişeze nu doar suma maximă, ci şi poziţiile de început şi de sfârşit ale secvenţei.

Număr de accesări: 18992

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

• 

  ana bordea 12-4-2016 13:44:18

  #include <iostream>
  using namespace std;
  int s, i, smax, a[100], n;
  int main()
  {
  cin>>n;
  for(i=1; i<=n; i++)
  cin>>a[i];
  for(i=1; i<=n; i++)
  smax=a[i];
  s=a[1];
  for(i=2; i<=n; i++)
  {
  s=s+a[i];
  if(s>smax)
  smax=s;
  if(s<0)
  s=0;
  }
  cout<<smax;
  return 0;
  }