CF1359D Yet Another Yet Another Task

Alice 和 Bob 又在玩一种新的纸牌游戏。这次的规则如下：桌上有 $n$ 张牌排成一行，第 $i$ 张牌的点数为 $a_i$。 首先，Alice 选择一个非空的连续牌段 $[l, r]$（$l \le r$）。随后，Bob 从这个牌段中移除一张牌 $j$（$l \le j \le r$）。游戏的得分为剩下牌段上所有牌的点数之和（即 $a_l + a_{l+1} + \dots + a_{j-1} + a_{j+1} + \dots + a_r$）。特别地，如果 Alice 选择的牌段只有一张牌，那么 Bob 移除这唯一的一张牌后，得分为 $0$。 Alice 希望让得分尽可能大，而 Bob 会选择让得分尽可能小的那张牌移除。 Alice 应该选择哪一段牌，使得最终得分最大？请输出最大得分。

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示牌的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-30 \le a_i \le 30$），表示每张牌上的点数。

输出一个整数，表示游戏的最终得分。

在第一个样例中，Alice 选择整个区间 $[1,5]$。Bob 从中移除第 $3$ 张牌，点数为 $10$。因此最终得分为 $5 + (-2) + (-1) + 4 = 6$。 在第二个样例中，Alice 选择区间 $[1,4]$，Bob 移除第 $1$ 张或第 $3$ 张牌，点数为 $5$，最终得分为 $5 + 2 + 3 = 10$。 在第三个样例中，Alice 可以选择任意一个长度为 $1$ 的区间：$[1,1]$、$[2,2]$ 或 $[3,3]$。Bob 移除唯一的一张牌后，得分为 $0$。如果 Alice 选择其他长度的区间，得分会小于 $0$。 由 ChatGPT 4.1 翻译