CF1933A Turtle Puzzle: Rearrange and Negate

给定一个包含 $n$ 个整数的数组 $a$。你需要对该数组依次执行以下两个操作（先执行第一个操作，再执行第二个操作）： 1. 可以任意重新排列数组中的元素，或者保持原有顺序不变。 2. 可以选择至多一个连续的元素区间，并将该区间内所有元素的符号取反。形式化地说，你可以选择一对下标 $l, r$，满足 $1 \le l \le r \le n$，然后对所有 $l \le i \le r$ 的 $a_i$ 执行 $a_i = -a_i$ 操作（即取反）。注意，你也可以选择不进行任何操作，保持所有元素符号不变。 在依次执行上述两个操作后，数组元素之和的最大值是多少？

输入的第一行为一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例的第一行为一个整数 $n$（$1 \le n \le 50$），表示数组 $a$ 的元素个数。 每个测试用例的第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-100 \le a_i \le 100$），表示数组 $a$ 的元素。

对于每个测试用例，输出依次执行上述两个操作后，数组元素和的最大值。

在第一个测试用例中，你可以先将数组重新排列为 $[3, -2, -3]$（操作1），然后选择 $l = 2, r = 3$，得到和为 $3 + -((-2) + (-3)) = 8$（操作2）。 在第二个测试用例中，你可以两次都不进行操作，得到和为 $0$。 在第三个测试用例中，你可以两次都不进行操作，得到和为 $0 + 1 = 1$。 在第四个测试用例中，你可以保持顺序不变（操作1），然后选择 $l = 1, r = 1$，得到和为 $-(-99) = 99$（操作2）。 在第五个测试用例中，你可以保持顺序不变（操作1），然后选择 $l = 2, r = 3$，得到和为 $10 + -((-2) + (-3)) + 7 = 22$（操作2）。 在第六个测试用例中，你可以保持顺序不变（操作1），然后选择 $l = 1, r = 5$，得到和为 $-((-1)+(-2)+(-3)+(-4)+(-5))=15$（操作2）。 由 ChatGPT 4.1 翻译