Fişierul intrare/ieşire:colier.in, colier.outSursăVianuarena
AutorDin FolclorAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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. 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 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 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