Suma2

suma2

== include(page="template/taskheader" task_id="suma2") ==

Profesorul de matematica i-a dat lui Gigel un sir de $N$ valori intregi, din intervalul {$[-10000,10000]$} si i-a cerut sa gaseasca un subsir al acestuia, cu proprietatea ca oricare $2$ elemente ale acestuia nu se afla pe pozitii alaturate in sirul initial, iar suma subsirului este maxima. Scrieti un program care sa rezolve problema lui Gigel.

Poveste si cerinta...

h2. Date de intrare

Pe prima linie a fisierului $suma2.in$ se afla numarul $N$ de elemente ale sirului. Pe urmatoarea linie se afla $N$ valori intregi (elementele sirului), separate prin spatii.

...

h2. Date de iesire

In fisierul $suma2.out$ veti afisa suma maxima a unui subsir al sirului dat, care are proprietatea precizata mai sus.
 

...

h2. Restrictii

* $1 ≤ N ≤ 200 000$
* Subsirul poate sa nu contina nici un element.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. suma2.in |_. suma2.out |

| 7
3 7 5 -1 6 6 2
| 16 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicatie

Subsirul cu suma $16$ contine elementele de pe pozitiile: $1,3,5,7$.

...

== include(page="template/taskfooter" task_id="suma2") ==

2142