[C++]Subsir de suma maxima

[AIM Katzuno Valoare]

Pentru inceput voi incepe spunand ca aceasta problema a fost data la OJI 2001 in judetul Mures.

ENUNT:

Subiectul 3 – Subsir de suma maxima

Se considera un sir de n (0<n<100) numere intregi, printre care exista cel putin un element pozitiv. Scrieti un program care determina secventa avand suma elementelor maxima. Validati datele de intrare.

Exemplu:

n=10

Sirul: 1 2 –6 3 4 5 –2 10 –5 –6

Rezultate:

Suma maxima: 20

Lungimea secventei: 5

Pozitia de inceput a secventei: 4

Pozitia de sfarsit a secventei: 8

Secventa avand suma 20: 3 4 5 –2 10

 

 

#include <iostream>
using namespace std;
 
int main() {
int i, v[501], n;
 
cout << "Lungimea sirului este: ";
cin >> n;//31
for (i = 1; i <= n; i++) {
cout << "V["<<i << "]=";
cin >> v[i];
}
int w[500];
int j;
int poz1, poz2;
w[1] = v[1];
for (i = 2; i <= n; i++)
{
if (v[i] > w[i - 1] + v[i])
w[i] = v[i];
else
w[i] = v[i] + w[i - 1];
}
poz1 = 1;
 
int max = w[1];
for (i = 1; i <= n; i++)
if (w[i] > max)
{
max = w[i];
poz1 = i;
 
}
poz2 = poz1;
int s = max;
while (s - v[poz2] != 0)
{
s = s - v[poz2];
poz2--;
 
}
 
cout << "Rezultate:" << "\n";
cout << "Suma maxima: " << max << "\n";
cout << "Lungimea secventei= " << poz1 - poz2 + 1 << "\n";
cout << "Pozitia de inceput a secventei este: " << poz2 << "\n";
cout << "Pozitia de sfarsit a secventei este: " << poz1 << "\n";
cout << "Secventa avand suma " << max << " este: ";
for (i = poz2; i <= poz1; i++)
cout << v[i] << " ";
return 0;
}

Nivel de dificultate: Incepator, dar mai mult decat cel care invata algoritmii elementari.

Daca aveti intrebari, nelamuriri puteti lasa un reply la acest topic, iar eu voi raspunde.

Edited December 15, 2013 by pH Katzuno

[AIM Katzuno Valoare]

[AIM Katzuno Valoare]

Mutat la sectiunea tutoriale.