← 返回题目列表

Codeforces · 1359/D

D. 又一个又一个任务

中文机器翻译题面 查看原题

Alice 和 Bob 正在玩另一个纸牌游戏。这次的规则如下。他们面前有一排 $$$n$$$ 卡片。第 $$$i$$$ 卡的价值为 $$$a_i$$$。

首先,Alice 选择一个非空的连续卡片段 $$$[l; r]$$$ ($$$l \le r$$$)。之后,Bob 从该段 $$$(l \le j \le r)$$$ 中删除一张卡片 $$$j$$$。游戏的得分为$$$(a_l + a_{l + 1} + \dots + a_{j - 1} + a_{j + 1} + \dots + a_{r - 1} + a_r)$$$段上剩余牌的总分。特别是,如果 Alice 选择只有一个元素的片段,那么 Bob 删除唯一一张卡片后的分数为 $$$0$$$。

Alice 想让分数尽可能大。鲍勃拿了一张分数尽可能小的牌。

Alice 应该选择哪个片段才能获得最大分数?输出最高分。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 卡的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-30 \le a_i \le 30$$$) — 卡片上的值。

输出

打印一个整数——游戏的最终得分。

示例

输入 #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

注意

在第一个示例中,Alice 选择了一段 $$$[1;5]$$$ — 整行卡片。 Bob 从段中删除了价值 $$$10$$$ 的卡 $$$3$$$。因此,最终得分为 $$$5 + (-2) + (-1) + 4 = 6$$$。

在第二个示例中,Alice 选择段 $$$[1;4]$$$,以便 Bob 删除值为 $$$5$$$ 的卡 $$$1$$$ 或 $$$3$$$,从而得到答案 $$$5 + 2 + 3 = 10$$$。

在第三个示例中,Alice 可以选择长度为 $$$1$$$ 的任意段:$$$[1;1]$$$、$$$[2;2]$$$ 或 $$$[3;3]$$$。鲍勃拿走了唯一的一张牌,因此得分为 $$$0$$$。如果 Alice 选择其他部分,那么答案将小于 $$$0$$$。