un mic subsir

[•cosser]

as vrea sa stiu cum pot sa gasesc un subsir cu suma maxima si sa-l si afisez, in timp liniar?
asta daca se poate, eu nu am nici o idee.
(suma maxima se poate gasi usor.)

Later edit: prin subsir am vrut sa spun subsecventa, scuze

[•pauldb]

Daca prin subsir intelegi subsecventa (adica pozitii consecutive) faci asa:

Calculezi S[ i ] = suma elementelor pe intervalul [1 ... i]. Suma pentru secventa [i+1, j] = S[ i ] - S[ j ]. Deci pentru un S[ i ], ne intereseaza S[ j ] minim, cu j < i, lucru ce il poti retine pe parcurs.

[•Pepelea_Flaviu]

Cod:

Suma pentru secventa [i+1, j] = S[ i ] - S[ j ]

vine S[ j ] - S[ i ]

[•ciuperca]

@sergiu


pai varule prin subsir se intelege submultime de elemente din sir luate in ordinea in care apar in sir

uite

daca vrei subsir pur si simplu faci acolo o suma cu numerele mai mari de 0

daca vrei subsir cu un numar fix de elemente (sa zicem k) tii un heap cu cele mai mari k numere si faci o suma pe heap la sfarsit dar asa ai o ( n log n )

[•Pepelea_Flaviu]

nu trebuie neaparat cu heap.....poate baga o sortare in O(n log n) si apoi sa adune cele mai mari k numere...

[•cosser]

mersi, a fost greseala mea de exprimare, m-am referit la o subsecventa.
asadar, raspunsul era sub nasul meu: sa retin acel minim pentru S[ i ]

[•Marius]

Dacă ai 1 milion de numere şi memorie O(1) nu mai merge cu acel vector. Poţi face însă cu câteva variabile.

Cod:

// variabile
best_sum, start, finish;
cur_sum, cur_start;

// iniaţializări
citeşte val
cur_sum = best_sum = val;
start = finish = cur_start = 1;

pentru i = 2, n execută
    citeşte val
    dacă cur_sum < 0 atunci
        cur_sum = val, cur_start = i
    altfel
        cur_sum = cur_sum + val
    dacă best_sum < cur_sum atunci
        best_sum = cur_sum, start = cur_start, finish = i

// ai în best_sum valoarea subsecv de sumă maximă iar în start şi finish începutul şi sfârşitul ei
// pentru afişare mai citeşti o dată datele de intrare

Sper să fie bine ce am scris. Văd că nu merge să scrii îngroşat în cod.

[•cosser]

ideea ta e foarte buna