← 返回题目列表

Codeforces · 1343/C

C. 交替子序列

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

回想一下,如果 $$$b$$$ 可以通过删除零个或多个元素而不改变剩余元素的顺序从 $$$a$$$ 导出,则序列 $$$b$$$ 是序列 $$$a$$$ 的子序列。例如,如果 $$$a=[1, 2, 1, 3, 1, 2, 1]$$$,则可能的子序列为:$$$[1, 1, 1, 1]$$$、$$$[3]$$$ 和 $$$[1, 2, 1, 3, 1, 2, 1]$$$,但不是 $$$[3, 2, 3]$$$ 和$$$[1,1,1,1,2]$$$。

给定一个序列 $$$a$$$,由 $$$n$$$ 正元素和负元素组成(序列中没有零)。

你的任务是选择给定序列的大小(长度)最大的交替子序列(即每个下一个元素的符号与当前元素的符号相反,如正-负-正等或负-正-负等)。在所有这样的子序列中,您必须选择一个具有最大元素和的子序列。

换句话说,如果交替子序列的最大长度是$$$k$$$,那么你的任务就是找到长度为$$$k$$$的某些交替子序列的最大元素和。

您必须回答 $$$t$$$ 独立测试用例。

输入

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

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$a$$$ 中的元素数量。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9, a_i \ne 0$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。

输出

对于每个测试用例,打印答案 — $$$a$$$ 的按大小(长度)交替子序列的最大值的最大总和。

示例

输入 #1

4
5
1 2 3 -1 -2
4
-1 -2 -1 -3
10
-2 8 3 8 -4 -15 5 -2 -3 1
6
1 -1000000000 1 -1000000000 1 -1000000000

输出 #1

2
-1
6
-2999999997

注意

在示例的第一个测试用例中,可能的答案之一是 $$$[1, 2, \underline{3}, \underline{-1}, -2]$$$。

在示例的第二个测试用例中,可能的答案之一是 $$$[-1, -2, \underline{-1}, -3]$$$。

在示例的第三个测试用例中,可能的答案之一是 $$$[\underline{-2}, 8, 3, \underline{8}, \underline{-4}, -15, \underline{5}, \underline{-2}, -3, \underline{1}]$$$。

在示例的第四个测试用例中,可能的答案之一是 $$$[\underline{1}, \underline{-1000000000}, \underline{1}, \underline{-1000000000}, \underline{1}, \underline{-1000000000}]$$$。