307463: CF1359D. Yet Another Yet Another Task
Memory Limit:512 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Yet Another Yet Another Task
题意翻译
**Alice**和**Bob**正在玩另一场卡牌游戏。这次的规则如下: 首先,**Alice**选取一段不为空的连续区间$[l,r],(l\leq r)$,之后**Bob**移去这个区间的一张卡牌$j(l\leq j \leq r)$。这场游戏的得分就是区间剩余卡牌值的总和。特别的,如果**Alice**只选择了一张牌,那么最终的得分就是0. **Alice**想让这个得分足够大,而**Bob**为了让得分足够小,会取出一张这个区间中值最大的牌。现在询问**Alice**应该如何选择这个区间来使得自己的得分在所有情况中最大。输出最大值。题目描述
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.
输入输出样例
输入样例 #1
5
5 -2 10 -1 4
输出样例 #1
6
输入样例 #2
8
5 2 5 3 -30 -30 6 9
输出样例 #2
10
输入样例 #3
3
-10 6 -15
输出样例 #3
0