infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Bula Ionut din Septembrie 19, 2008, 15:57:32


Titlul: un mic subsir
Scris de: Bula Ionut din Septembrie 19, 2008, 15:57:32
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

Titlul: Răspuns: un mic subsir
Scris de: Paul-Dan Baltescu din Septembrie 19, 2008, 16:15:09
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.

Titlul: Răspuns: un mic subsir
Scris de: Flaviu Pepelea din Septembrie 19, 2008, 19:15:10
Cod:
Suma pentru secventa [i+1, j] = S[ i ] - S[ j ]
vine S[ j ] - S[ i ]

Titlul: Răspuns: un mic subsir
Scris de: Nad Acrepuic din Septembrie 19, 2008, 20:31:14
@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 )

Titlul: Răspuns: un mic subsir
Scris de: Flaviu Pepelea din Septembrie 19, 2008, 21:23:28
nu trebuie neaparat cu heap.....poate baga o sortare in O(n log n) si apoi sa adune cele mai mari k numere...

Titlul: o mica mare greseala
Scris de: Bula Ionut din Septembrie 19, 2008, 22:20:04
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 ]


Titlul: Răspuns: un mic subsir
Scris de: Marius Stroe din Septembrie 20, 2008, 09:27:20
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.

Titlul: Răspuns: un mic subsir
Scris de: Bula Ionut din Septembrie 20, 2008, 17:21:02
ideea ta e foarte buna     :peacefingers:


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines