题目重述

给定一个长度为 $n$ 的整数数组 $a$，必须依次执行两个操作：

1. 任意重排数组元素（也可以保持原顺序）。
2. 选择至多一个连续子段，将该子段内所有元素符号取反。

目标：最大化最终数组的元素和。

---

详细题解

第一步：关键观察

两个操作都不会改变任何一个元素的 绝对值。

• 重排：只是改变位置，不影响值的大小和符号。
• 取反一个连续子段：只改变子段内元素的符号，绝对值不变。

因此，无论怎么操作，每个元素 $a_i$ 最终都会变成 $+ |a_i|$ 或 $-|a_i|$，绝对值固定，符号可选（但有约束）。

---

第二步：约束分析

取反操作只能作用于 一个连续子段。
但因为有 重排 操作，我们可以先重排，把想要取反的元素全部放到一起，形成一个连续段，然后对这个段取反。

换句话说：
重排 + 一个连续段取反 等价于 可以选择任意一个子集 $S$ 中的元素取反，只要这些元素在重排后能连续。
由于重排可以把任意一组元素放在一起，所以我们可以选择 任意子集 取反。

那么问题变成：
我们可以选择任意一组元素，把它们从原来的符号变成相反符号，其他元素符号不变。
目标是最大化总和。

---

第三步：如何选择取反集合

• 如果一个数原来是负数 $a_i < 0$，不取反时贡献 $a_i$（负值），取反后贡献 $-a_i = |a_i|$（正值），收益为 $2|a_i|$。
• 如果一个数原来是正数 $a_i > 0$，不取反时贡献 $a_i$（正值），取反后贡献 $-a_i$（负值），收益为 $-2a_i$（亏损）。
• 如果 $a_i = 0$，取反与否不影响。

因此，为了最大化总和，我们应该只取反负数，不取反正数。
取反所有负数，使它们变成正数。

---

第四步：可达性

我们能否同时取反 所有负数？

可以。先重排数组，使所有负数排在前面，所有非负数（包括 $0$ 和正数）排在后面。
然后取反从第一个负数到最后一个负数的这一段连续子段（即前缀）。
如果数组中没有负数，则不需要执行取反操作。

这样操作后：

• 原来的负数变成正数。
• 原来的正数和零保持不变。

最终数组的所有元素都 $\ge 0$。

---

第五步：最终答案

最终数组的和为： [ |a_1| + |a_2| + \dots + |a_n| ] 因为每个数都变成了它的绝对值。

并且这是最大值，因为绝对值固定，任何其他选择都会使至少一个负数保持负值（减少总和）或使一个正数变负（减少总和）。

---

第六步：算法步骤

对于每个测试用例：

1. 读入 $n$ 和数组 $a$。
2. 计算 $sum = \sum_{i=1}^n |a_i|$。
3. 输出 $sum$。

时间复杂度：$O(n)$，空间复杂度：$O(1)$ 额外空间。

---

示例验证

样例 1

$a = [-2, 3, -3]$
$|{-2}| + 3 + |{-3}| = 2 + 3 + 3 = 8$ ✅

样例 5

$a = [10, -2, -3, 7]$
$10 + 2 + 3 + 7 = 22$ ✅

样例 6

$a = [-1, -2, -3, -4, -5]$
$1 + 2 + 3 + 4 + 5 = 15$ ✅

---

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            sum += abs(x);
        }
        cout << sum << "\n";
    }
    return 0;
}