Fişierul intrare/ieşire:	colier2.in, colier2.out	Sursă	Vianuarena
Autor	Din Folclor	Adăugată de	Cristian Francu •francu
Timp execuţie pe test	0.5 sec	Limită de memorie	1024 kbytes
Scorul tău	N/A	Dificultate	4/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Colier 2 (clasa a 9-a)

Notă: această problemă este o modificare a problemei colier. Are acelaşi enunţ, dar limita de memorie a fost micşorată.

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.

Date de intrare

Fişierul de intrare colier2.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 colier2.out se va scrie valoarea maximă care poate fi obţinută prin extragerea unui număr de pietre aflate pe poziţii consecutive.

Restricţii

• 1 ≤ N ≤ 1000000
• -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ă)

Exemplu