Yet Another Yet Another Task
Contest: Educational Codeforces Round 88 (Rated for Div. 2)
Difficulty rating: 2000
Tags: data structures, dp, implementation, two pointers

Alice and Bob are playing yet another card game. This time the rules are the following. There are $$$n$$$ cards lying in a row in front of them. The $$$i$$$-th card has value $$$a_i$$$.

First, Alice chooses a non-empty consecutive segment of cards $$$[l; r]$$$ ($$$l \le r$$$). After that Bob removes a single card $$$j$$$ from that segment $$$(l \le j \le r)$$$. The score of the game is the total value of the remaining cards on the segment $$$(a_l + a_{l + 1} + \dots + a_{j - 1} + a_{j + 1} + \dots + a_{r - 1} + a_r)$$$. In particular, if Alice chooses a segment with just one element, then the score after Bob removes the only card is $$$0$$$.

Alice wants to make the score as big as possible. Bob takes such a card that the score is as small as possible.

What segment should Alice choose so that the score is maximum possible? Output the maximum score.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of cards.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-30 \le a_i \le 30$$$) — the values on the cards.

Output format:
Print a single integer — the final score of the game.

Constraints:
Time limit: 1.5 s
Memory limit: 512.0 MB

Note:
In the first example Alice chooses a segment $$$[1;5]$$$ — the entire row of cards. Bob removes card $$$3$$$ with the value $$$10$$$ from the segment. Thus, the final score is $$$5 + (-2) + (-1) + 4 = 6$$$.

In the second example Alice chooses a segment $$$[1;4]$$$, so that Bob removes either card $$$1$$$ or $$$3$$$ with the value $$$5$$$, making the answer $$$5 + 2 + 3 = 10$$$.

In the third example Alice can choose any of the segments of length $$$1$$$: $$$[1;1]$$$, $$$[2;2]$$$ or $$$[3;3]$$$. Bob removes the only card, so the score is $$$0$$$. If Alice chooses some other segment then the answer will be less than $$$0$$$.

Example input:
5
5 -2 10 -1 4

Example output:
6

Example input:
8
5 2 5 3 -30 -30 6 9

Example output:
10

Editorial:
Alice wants to choose such a segment $$$[l; r]$$$ that $$$\sum \limits_{l \le i \le r} a_i - \max \limits_{l \le i \le r} a_i$$$ is maximum possible.
There is a well-known problem where you have to find a segment with maximum $$$\sum \limits_{l \le i \le r} a_i$$$. That problem is solved with Kadane algorithm. Let's learn how to reduce our problem to that one.
Notice that the values in the array are unusually small. Let's iterate over the maximum value on segment. Let $$$mx$$$ be the current value. If we make all $$$a_i$$$ such that $$$a_i > mx$$$ equal to $$$-\infty$$$, then it will never be optimal to take them in a segment. Find the maximum sum subarray in that modified array and update the answer with its $$$sum - mx$$$.
Notice that you can ignore the fact if there is a value exactly equal to $$$mx$$$ on the maximum sum segment. If there isn't then you'll update the answer with a smaller value than the actual one. Let the actual maximum on the maximum sum segment be some $$$y$$$. You can see that for any value between $$$y$$$ and $$$mx$$$ the maximum sum segment will always be that chosen one. Thus, when you reach $$$y$$$, you'll update the answer with the correct value.
Overall complexity: $$$O(\max a_i \cdot n)$$$.