Atenție! Aceasta este o versiune veche a paginii., scrisă la 2016-09-09 18:01:27.
Revizia anterioară   Revizia următoare  

Fișierul intrare/ieșire colier.in, colier.out Sursă Vianuarena
Autor din folclor Adăugată de avatar vmanz Victor Manz vmanz
Timp de execuție pe test 0.5 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Colier (clasa a 9-a)

De ziua îndrăgostiților Macarie s-a gândit să-i cumpere Petronelei un colier. Cum însă nu are foarte mulți bani, a apelat la un magazin online ieftin (și bun). Din păcate colierul primit, format din N pietre prețioase are și defecte. Pentru fiecare piatră prețioasă se cunoaște nivelul de frumusețe (care poate fi un număr negativ în cazul defectelor). Macarie vrea să păstreze doar o parte din pietrele prețioase, astfel încât să obțină un colier cât mai frumos. Pietrele păstrate trebuie să fi fost pe poziții consecutive în colierul inițial. Macarie nu se pricepe foarte bine la calcule și vă cere ajutorul. Ar vrea să știe nivelul maxim de frumusețe pe care-l poate obține din colierul dat prin extragerea unui număr de pietre aflate pe poziții consecutive.

Date de intrare

Fișierul de intrare colier.in conține pe prima linie N = numărul de pietre din colierul dat, iar pe următoarele N linii câte un număr întreg reprezentând nivelul de frumusețe al fiecărei pietre prețioase.

Date de ieșire

În fișierul de ieșire colier.out vor fi scrise, pe prima linie valoarea maxima care poate fi obtinuta prin extragerea unui numar de pietre aflate pe pozitii consecutive.

Restricții

  • 1 ≤ N ≤ 1000000
  • -1000 ≤ nivelul de frumusete al fiecarei pietre pretioase ≤ 1000
  • Colierul este un sir circular. Pot fi alese un numar de pietre aflate la inceputul sirului afisat impreuna cu un numar de pietre aflate la sfarsit
  • Macarie trebuie sa selecteze cel putin o piatra pretioasa

Exemplu

colier.in colier.out
6 1 0 -5 2 -8 1
2

Explicație

Nivelul maxim de frumusete care se poate obtine este 2. Exista trei variante de obtinere a acestuia: Selectand prima si ultima piatra, sau selectand primele doua si ultima piatra, sau alegand doar piatra cu valoarea 2, aflata pe pozitia 4.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii