CF1343C Alternating Subsequence

回忆一下，如果序列 $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$ 组独立的测试数据。

输入的第一行包含一个整数 $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$ 的元素。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

对于每组测试数据，输出一个答案，即长度最大的交错子序列中元素和的最大值。

在第一个样例中，其中一个可能的答案是 $[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}]$。 由 ChatGPT 4.1 翻译