← 返回题目列表

Codeforces · 2064/C

C. 移除末端

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

您有一个长度为 $$$n$$$ 的数组 $$$a$$$,其中包含 非零 整数。最初,您有 $$$0$$$ 硬币,您将执行以下操作,直到 $$$a$$$ 为空:

  • 令 $$$m$$$ 为 $$$a$$$ 的当前大小。选择一个整数$$$i$$$,其中$$$1 \le i \le m$$$,获得$$$|a_i|$$$$$$^{\text{*}}$$$硬币,然后:
    • 如果$$$a_i \lt 0$$$,则将$$$a$$$替换为$$$[a_1,a_2,\ldots,a_{i - 1}]$$$(即删除以$$$a_i$$$开头的后缀);
    • 否则,将 $$$a$$$ 替换为 $$$[a_{i + 1},a_{i + 2},\ldots,a_m]$$$ (即删除以 $$$a_i$$$ 结尾的前缀)。

找出该过程结束时您可以拥有的最大硬币数量。

$$$^{\text{*}}$$$这里$$$|a_i|$$$表示$$$a_i$$$的绝对值:当$$$a_i \gt 0$$$时等于$$$a_i$$$,当$$$a_i \lt 0$$$时等于$$$-a_i$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$, $$$a_i \ne 0$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出过程结束时您可以拥有的最大硬币数量。

示例

输入
复制

3
6
3 1 4 -1 -5 -9
6
-10 -3 -17 1 19 20
1
1

输出
复制

23
40
1

注意

第一个测试用例中如何获取$$$23$$$硬币的示例如下:

  • $$$a = [3, 1, 4, -1, -5, \color{red}{-9}] \xrightarrow{i = 6} a = [3, 1, 4, -1, -5]$$$,并获得 $$$9$$$ 硬币。
  • $$$a = [\color{red}{3}, 1, 4, -1, -5] \xrightarrow{i = 1} a = [1, 4, -1, -5]$$$,并获得 $$$3$$$ 硬币。
  • $$$a = [\color{red}{1}, 4, -1, -5] \xrightarrow{i = 1} a = [4, -1, -5]$$$,并获得 $$$1$$$ 硬币。
  • $$$a = [4, -1, \color{red}{-5}] \xrightarrow{i = 3} a = [4, -1]$$$,并获得 $$$5$$$ 硬币。
  • $$$a = [4, \color{red}{-1}] \xrightarrow{i = 2} a = [4]$$$,并获得 $$$1$$$ 硬币。
  • $$$a = [\color{red}{4}] \xrightarrow{i = 1} a = []$$$,并获得$$$4$$$硬币。
完成所有操作后,您有$$$23$$$硬币。

在第二个测试用例中如何获取$$$40$$$硬币的示例如下:

  • $$$a = [-10, -3, -17, \color{red}{1}, 19, 20] \xrightarrow{i = 4} a = [19, 20]$$$,并获得 $$$1$$$ 硬币。
  • $$$a = [\color{red}{19}, 20] \xrightarrow{i = 1} a = [20]$$$,并获得 $$$19$$$ 硬币。
  • $$$a = [\color{red}{20}] \xrightarrow{i = 1} a = []$$$,并获得$$$20$$$硬币。
完成所有操作后,您将获得$$$40$$$金币。