问题的两个版本是不同的。您可能想阅读这两个版本。只有两个版本都解决了,你才能进行黑客攻击。
给你一个长度为 $$$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$$$ 的答案。