CF1747A Two Groups

给定一个包含 $n$ 个整数的数组 $a$。你需要将这 $n$ 个整数分成两个组 $s_1$ 和 $s_2$（组可以为空），使得满足以下条件： - 对于每个 $i$ $(1 \leq i \leq n)$，$a_i$ 恰好属于一个组。 - $|sum(s_1)| - |sum(s_2)|$ 的值在所有分组方式中最大。这里 $sum(s_1)$ 表示组 $s_1$ 中所有数的和，$sum(s_2)$ 表示组 $s_2$ 中所有数的和。 请你求出 $|sum(s_1)| - |sum(s_2)|$ 的最大可能值。

输入包含多组测试数据。第一行包含一个整数 $t$ $(1 \leq t \leq 2 \cdot 10^4)$，表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$，表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ $(-10^9 \leq a_i \leq 10^9)$，表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示 $|sum(s_1)| - |sum(s_2)|$ 的最大可能值。

在第一个测试用例中，可以分组为 $s_1 = \{10\}$，$s_2 = \{-10\}$。此时值为 $|10| - |-10| = 0$。 在第二个测试用例中，可以分组为 $s_1 = \{0, 11, -1\}$，$s_2 = \{-2\}$。此时值为 $|0 + 11 - 1| - |-2| = 10 - 2 = 8$。 在第三个测试用例中，可以分组为 $s_1 = \{2, 3, 2\}$，$s_2 = \{\}$。此时值为 $|2 + 3 + 2| - |0| = 7$。 在第四个测试用例中，可以分组为 $s_1 = \{-9, -4, 0\}$，$s_2 = \{2, 0\}$。此时值为 $|-9 - 4 + 0| - |2 + 0| = 13 - 2 = 11$。 由 ChatGPT 4.1 翻译