CF1343C.Alternating Subsequence

Recall that the sequence $b$ is a a subsequence of the sequence $a$ if $b$ can be derived from $a$ by removing zero or more elements without changing the order of the remaining elements. For example, if $a=[1, 2, 1, 3, 1, 2, 1]$, then possible subsequences are: $[1, 1, 1, 1]$, $[3]$ and $[1, 2, 1, 3, 1, 2, 1]$, but not $[3, 2, 3]$ and $[1, 1, 1, 1, 2]$.

You are given a sequence $a$ consisting of $n$ positive and negative elements (there is no zeros in the sequence).

Your task is to choose maximum by size (length) alternating subsequence of the given sequence (i.e. the sign of each next element is the opposite from the sign of the current element, like positive-negative-positive and so on or negative-positive-negative and so on). Among all such subsequences, you have to choose one which has the maximum sum of elements.

In other words, if the maximum length of alternating subsequence is $k$ then your task is to find the maximum sum of elements of some alternating subsequence of length $k$.

You have to answer $t$ independent test cases.

回忆一下，若序列 $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]$ 不是其子序列。

给定一个由 $n$ 个非零整数（即全为正数或负数，不含零）构成的序列 $a$。

你的任务是：在该序列中选出一个长度最大的交替子序列（即每个后续元素的符号与当前元素符号相反，如“正-负-正-…”或“负-正-负-…”）。在所有满足该最大长度的交替子序列中，你需要选出元素和最大的一个。

换言之，若最长交替子序列的长度为 $k$，则你的任务是找出某个长度为 $k$ 的交替子序列，使其元素之和最大。

你需要回答 $t$ 个相互独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9, a_i \ne 0$), where $a_i$ is the $i$-th element of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).

输入的第一行包含一个整数 $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$）。

For each test case, print the answer — the maximum sum of the maximum by size (length) alternating subsequence of $a$.

对于每个测试用例，输出答案——即数组 $a$ 的最长（按长度计算）交替子序列的最大和。

In the first test case of the example, one of the possible answers is $[1, 2, \underline{3}, \underline{-1}, -2]$.

In the second test case of the example, one of the possible answers is $[-1, -2, \underline{-1}, -3]$.

In the third test case of the example, one of the possible answers is $[\underline{-2}, 8, 3, \underline{8}, \underline{-4}, -15, \underline{5}, \underline{-2}, -3, \underline{1}]$.

In the fourth test case of the example, one of the possible answers is $[\underline{1}, \underline{-1000000000}, \underline{1}, \underline{-1000000000}, \underline{1}, \underline{-1000000000}]$.

在示例的第一个测试用例中，一个可能的答案是 $[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}]$。