Preparando MOJI
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.
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.
Print a single integer — the final score of the game.
5 5 -2 10 -1 4
6
8 5 2 5 3 -30 -30 6 9
10
3 -10 6 -15
0
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$$$.
Informação
Provedor Codeforces
Código CF1359D
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:02:47
Relacionados