← 返回题目列表

Codeforces · 1984/C1

C1. 幅度(简单版)

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

问题的两个版本是不同的。您可能想阅读这两个版本。只有两个版本都解决了,你才能进行黑客攻击。

给你一个长度为 $$$n$$$ 的数组 $$$a$$$。从 $$$c = 0$$$ 开始。然后,对于从 $$$1$$$ 到 $$$n$$$ (按递增顺序)的每个 $$$i$$$ 执行以下操作之一:

- 选项 $$$1$$$:将 $$$c$$$ 设置为 $$$c + a_i$$$。
- 选项 $$$2$$$:将 $$$c$$$ 设置为 $$$|c + a_i|$$$,其中 $$$|x|$$$ 是 $$$x$$$ 的绝对值。

令$$$c$$$ 经过上述过程后的最大最终值等于$$$k$$$。找到$$$k$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$)。

每个 case 的第二行包含 $$$n$$$ 整数 $$$a_1$$$、$$$a_2$$$、$$$a_3$$$、$$$\ldots$$$、$$$a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$)。

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

输出

对于每个测试用例,输出一个整数 - $$$k$$$ 的值。

示例

输入 #1

5
4
10 -9 -3 4
8
1 4 3 4 1 4 3 4
3
-1 -2 -3
4
-1000000000 1000000000 1000000000 1000000000
4
1 9 8 4

输出 #1

6
24
6
4000000000
22

注意

在第一个测试用例中,如果我们每次相加时都将 $$$c$$$ 设置为其绝对值,则最终会得到 $$$6$$$。可以证明这是最大的结果。

在第二个测试用例中,取绝对值永远不会改变任何东西,因此我们只需对数组求和即可得到 $$$24$$$。

在第三个测试用例中,最好等到最后将 $$$c$$$ 设置为其绝对值,从而得到 $$$6$$$ 的答案。