== include(page="template/taskheader" task_id="colier") ==
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.
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. Colierul este circular, ceea ce înseamnă că după ultima piatră urmează prima. Frumusețea colierului rezultat este suma frumuseților pietrelor selectate.
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.
h2. Date de intrare
Fișierul de intrare $colier.in$ contine pe prima linie N = numarul de pietre din colierul dat, iar pe urmatoarele N linii cate un numar intreg reprezentand nivelul de frumusete al fiecarei pietre pretioase.
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.
h2. 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.
În fișierul de ieșire $colier.out$ se va scrie valoarea maximă care poate fi obținută prin extragerea unui număr de pietre aflate pe poziții consecutive.
h2. 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$
* $-1000 ≤ nivelul de frumusețe al fiecărei pietre pretioase ≤ 1000$
* Colierul este un șir circular. Pot fi alese un număr de pietre aflate la începutul șirului afișat împreună cu un număr de pietre aflate la sfârșit
* Macarie trebuie să selecteze cel puțin o piatră pretioasă (colierul format va avea cel puțin o piatră)
h2. Exemplu
table(example).
|_. colier.in |_. colier.out |
table(example).
|_. colier.in |_. colier.out |_. Explicație |
| 7
-2
1
2
-1
0
1
-2
| 3
| Nivelul maxim de frumusețe care se poate obține este 3, selectând pietrele de la
poziția 2 la poziția 3 sau pietrele de la 2 la poziția 6.
|
| 6
1
0
-5
2
-8
1
1
0
-5
2
-8
1
| 2
|
h3. 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.
| Nivelul maxim de frumusețe care se poate obține este 2, selectând prima și ultima piatră,
sau selectând primele două și ultima piatră, sau alegând doar piatra cu valoarea 2, aflată
pe poziția 4.
|
== include(page="template/taskfooter" task_id="colier") ==
