Fişierul intrare/ieşire:colier2.in, colier2.outSursăVianuarena
AutorDin FolclorAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.5 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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

colier.incolier.outExpplicaţ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
2
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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici