035 Subsecventa de suma maxima

[•MBlue]

iau 95 de puncte pentru ca am rezultat incorect la a doua rulare

datele de intrare sunt:
15
-1 7 5 0 -7 -9 0 8 -2 5 -2 1 4 9 1

si rezultatul programului meu:
24 8 15

ce nu este in regula?

[•gabitzish1]

Daca ai mai multe subsecvente cu aceeasi suma, trebuie afisata cea cu indicele de inceput mai mic. Tu mai ai un 0 pe pozitia 7, pe care daca il adaugi la subsecventa iti da aceeasi suma, dar indice mai mic.
Raspunsul e 24 7 15.

[•MBlue]

da eu am inteles exact inversul din enunt. iti multumesc o sa modific acum

[•catalin93]

Am si eu o intrebare... ce ar trebui adaugat la o sursa care merge in O(n) (sper  ) http://infoarena.ro/job_detail/279341?action=view-source ca sa aleaga subsecventa care are minim k elemente? 

[•gabitzish1]

Inca o conditie... if (poz_final- poz_inceput + 1 >= k)

L.E. : My bad... m'am grabit.

[•Florian]

Am impresia ca asa, risti sa nu iti gaseasca nicio secventa. Cred ca e nevoie de un deque. Gresesc? 

LE: De exemplu, daca toate elementele sunt negative, nu merge. [ ca lungimea sumei curente va fi mereu 1]

[•devilkind]

Nu gresesti. Nu e de ajuns acea conditie. Daca ai numai elemente negative spre exemplu nu o sa iti gaseasca nimic. Nu cred ca e nevoie de deque, cred ca e de ajuns un minim.

[•catalin93]

bun si in concluzie daca merg cu un k si in mom in care suma devine negativa il resetez nu merge...
cum ar trebui sa fac ca sa ia si cazul in care spre ex am :
(n k si numerele)

Cod:

4 4 
-2 -3 -4 -5

la asta raspunsul ar trebui sa fie -14 1 4 .. ce ar trebui sa adaug ?   

[•pauldb]

Ar trebui sa ai variabila pentru solutie initializata cu maximul dintre numerele din vector.

[•wefgef]

@catalin93: Solutia ta nu se poate adapta pentru a gasi subsecventa de suma maxima de lungime cel putin K. Trebuie sa folosesti o solutie ce are complexitatea de memorie O(N) (sau O(K), daca vrei sa optimizezi memoria).

[•cristiprg]

pana la urma cu ce ar trebui sa citim/afisam, ca sa fie timpul cat mai scurt? ... cu streamuri sau cu scanf() / printf() ?

[•AnDrEwBoY]

Pe calculatoarele actuale nu prea conteaza,in general nu se face diferenta pe citire ci pe eficienta.

[•rusu_radu]

Nu intzeleg dc numi  ia primele 3 teste... is cele mai mici... atzi putea sami spunetzi ce caz special au... nu pot sami dau seama dc nu le iau:D

[•anna_bozianu]

Banuiesc ca nu verifici initial daca toate valorile sunt negative.

[•rusu_radu]

MSM unu din cazurile pe care le scapa asta era... la celelalte 2 teste am fost eu banana...) la mine daca subsecventza se termina pe ultima pozitzie nu mai facea testul sa vada daca nu cumva secventza care se termina acolo e cea mai mare... oricum mersi mult:-*

[•bugy]

  foarte dragut... pentru o sursa pe care am luat 100 acum am luat 90 dupa care 85 .. dupa caree 80 .. faza e ca pe unele teste. ia 2,19.. deci nu depaseste 2,2...

[•crisojog]

am si eu o problema.. pe o sursa de complexitate O(n) cu citirea facuta in <stdio.h> iau 95.. de ce?.. iau tle pe ultimu test..    ceva e dubios

[•crisojog]

cum se poate sa iau 90 pe aceeasi sursa pe care acum 10 min luam 95?
repet.. citirea e facuta cu scanf..
spuneti-mi pls macar sa nu fiu ca in bancul cu nebunul de pe autostrada..

[•c_e_manu]

S-a mai vorbit de asta pe forum. Ai o sursa ce e la limita si uneori intra, alteori nu. 

[•crisojog]

S-a mai vorbit de asta pe forum. Ai o sursa ce e la limita si uneori intra, alteori nu. 

1.shi in caz de concurs ce as face?
2.daca exista o metoda mai putin complexa decat asta pls tell me..

[•c_e_manu]

Pe compilatorul de pe infoarena, din ce am retinut, sunt mai rapide streamurile. Schimba la streamuri sa vezi daca mai ai probleme cu incadrarea in timp. 

[•Florian]

E cam stransa limita de timp. Adica, eu ar zic ca ar trebui sa intre si cu scanf, ca doar e problema din arhiva educationala. Deci, daca ati putea mari limita de timp astfel incat sa intre O(N) cu scanf, si sa nu intre o solutie de complexitate mai mare, ar fi ok, dupa parerea mea. 

[•AnDrEwBoY]

Intra in O(n) si cu scanf/printf

[•andunhill]

Cat da pe testul   " 4 
                           4 11 -10 1" ?
 

[•gabitzish1]

15 1 2