Problem G
Decelerating Jump
An athlete is participating in a new sport that is the perfect mix of hopscotch and triple jumping. For this jury sport, $n$ squares are laid out on the ground in a line, with equal distances between them. The first phase is the approach, where an athlete sprints towards the first square, in which they start their first jump. Then, they may jump on any number of other squares, and must finally land in the last square.
The jury has given a predetermined number of points to jumping in each square, and the score of the athlete will be the sum of the scores of all the squares they jump in, including the very first and last squares.
Due to the nature of this sport, once the athlete starts jumping, they can not accelerate anymore, and the length of consecutive jumps can never increase. Naturally, it is also impossible to reverse direction.
Given the points the jury has allocated to each square, find the maximal possible score an athlete can get on this event.
Input
The input consists of:
-
One line with an integer $n$ ($2\leq n\leq 3000$), the number of squares.
-
One line with $n$ integers $p_1, p_2, \dots , p_ n$ ($-10^9\leq p_ i\leq 10^9$), the number of points the jury awards for jumping on each of the squares.
Output
Output the maximum score that an athlete can get.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 -1 1 1 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 1 1 -1 1 |
2 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 -1 1 -1 |
-1 |
| Sample Input 4 | Sample Output 4 |
|---|---|
3 -1 -1 -1 |
-2 |
