gold
There are N
magical boxes along a road, each of which has a certain amount of gold: in the
k
-th box there is exactly gk
kilogram gold (k=1...N
).
If we get the gold from a box then the neighbouring boxes slide away. The boxes are in far away from each other,
so we cannot get the gold from two or more boxes at the same time. What is the maximal amount of gold (M) that we
can get?
Example
N: 5
gold in the boxes: 3 7 5 4 2
by exploring all possible ways, one can see that M=11
:
box id gold
1,3,5 3+5+2
1,4 3+4
2,4 7+4 -> max
2,5 7+2
Input Specification
N
g1 ... gN
The first line with the number 1 ≤ N ≤ 104
and the second line with the comma
separated numbers 1 ≤ gk ≤ 104 (k=1...N)
.
Output Specification
M
A single line with the required M
.
Sample Input 1
5
3 7 5 4 2
download as text file
Sample Output 1
11
download as text file
Sample Input 2
7
1 2 3 3 2 2 1
download as text file
Sample Output 2
7
download as text file