喵~ 主人你好呀！今天又是充满活力的一天，准备好和本喵一起解决这道有趣的题目了吗？这道题看起来有点小复杂，但只要跟着本喵的思路，你就会发现它其实是一只温顺的小猫咪哦！🐾

题目大意

这道题是说，我们有一个由 n 个整数组成的数组 a。我们可以进行一种操作任意次：选择两个相邻的元素，然后同时把它们的符号翻转（正数变负数，负数变正数）。我们的目标是，通过这些操作，让整个数组所有元素的和变得最大，然后输出这个最大的和，喵~

举个例子：数组是 [-1, -1, -1]。我们选择前两个元素 (-1, -1) 进行操作，它们就变成了 (1, 1)，数组就成了 [1, 1, -1]。这样一来，总和就从 -3 变成了 1，是不是好多了呀？

题解方法

想让总和最大，我们的第一反应肯定是希望数组里所有的数都变成非负数（也就是正数或者 0），对不对呀？这样加起来肯定最大嘛！所以问题就变成了：我们能不能通过这个操作，把所有负数都变成正数呢？

让我们来仔细研究一下这个操作，喵~

操作是选择相邻的 a[i] 和 a[i+1]，同时翻转它们的符号。

• 如果我们对 (a[i], a[i+1]) 操作一次，它们变成了 (-a[i], -a[i+1])。
• 如果我们紧接着对 (a[i+1], a[i+2]) 操作一次，a[i+1] 又被翻转了回来！-a[i+1] 变成了 a[i+1]。

发现了什么吗？连续对 (i, i+1) 和 (i+1, i+2) 操作，效果等同于只翻转了 a[i] 和 a[i+2] 的符号，中间的 a[i+1] 被翻转了两次，等于没变！通过这种“接力”的方式，我们可以把翻转效果传递下去。这意味着，我们可以翻转任意两个位置的元素的符号，而不仅仅是相邻的元素！ ✨

这个发现可太重要啦！现在问题就简化成了：我们可以任意选择成对的元素进行符号翻转。

每次操作我们都翻转两个数的符号。那么数组里负数的数量会怎么变化呢？

1. 翻转两个正数 (+, +) -> (-, -)：负数数量 +2。
2. 翻转两个负数 (-, -) -> (+, +)：负数数量 -2。
3. 翻转一正一负 (+, -) -> (-, +)：负数数量不变。

看出来了吗？每次操作，负数的数量要么增加 2，要么减少 2，要么不变。也就是说，负数数量的奇偶性是永远不会改变的！ 这在算法里叫做不变量 (Invariant)，是一个非常重要的性质哦！

有了这个结论，我们就可以分情况讨论啦：

情况一：初始时，数组里负数的个数是偶数

既然负数的个数是偶数，我们可以把它们两两配对。对每一对负数进行一次操作，它们就都变成正数啦！因为偶数个负数总能配成整数对，所以我们可以把所有负数都消灭掉，让它们全部变成正数。 这种情况下，最大的和就是数组里所有元素的绝对值之和。

情况二：初始时，数组里负数的个数是奇数

因为负数数量的奇偶性不变，所以不管我们怎么操作，最后数组里至少会留下一个负数（1, 3, 5... 个）。为了让总和最大，我们当然是希望只留下 1 个负数啦。 那么，应该留下哪个数作为负数呢？当然是那个对总和影响最小的数啦！也就是那个绝对值最小的数。 所以，在这种情况下，我们先把所有数都当成正数加起来（也就是所有元素的绝对值之和），然后减去两倍的最小绝对值。（为什么要减两倍呢？因为我们先把它按正数加进去了，现在要把它变成负数，所以要先减掉它本身，再减掉一次，才等于加上它的负值嘛。sum + |x| - 2*|x| = sum - |x|）。

一个特殊的例外：如果数组里有 0 怎么办？

如果数组里有一个或多个 0，上面那个“奇偶性不变”的规律就被打破了，喵！ 我们可以选任何一个负数 a[i] 和一个 0 a[j] 进行操作。a[i] 变成了正数，而 0 翻转符号后还是 0。这样，我们只用了一次操作就消灭了一个负数，负数的数量从奇数变成了偶数！ 一旦负数数量变成偶数，我们就可以回到情况一，把所有剩下的负数都变成正数。 所以，只要数组里有 0，无论开始有多少个负数，我们总能把它们全部变成非负数。

总结一下我们的策略：

1. 统计数组中负数的个数 neg_count 和是否存在 0。
2. 计算所有元素的绝对值之和 total_sum，并找到最小的绝对值 min_abs。
3. 如果 neg_count 是偶数，或者数组中存在 0，那么最大和就是 total_sum。
4. 如果 neg_count 是奇数，并且数组中没有 0，那么最大和就是 total_sum - 2 * min_abs。

是不是很简单清晰了呀？下面我们来看看代码是怎么实现这个思路的。

题解

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <limits>

// 这是解决单个测试用例的函数哦
void solve() {
    int n;
    std::cin >> n;

    long long total_sum = 0;
    int neg_count = 0;
    long long min_abs = std::numeric_limits<long long>::max();
    bool has_zero = false;

    // 我们不需要真的存下整个数组，可以一边读一边处理，省空间喵
    for (int i = 0; i < n; ++i) {
        long long val;
        std::cin >> val;

        // 如果是负数，计数器就+1
        if (val < 0) {
            neg_count++;
        }
        // 如果是0，就做个标记
        if (val == 0) {
            has_zero = true;
        }

        // 计算绝对值
        long long abs_val = std::abs(val);
        // 累加到总和里
        total_sum += abs_val;
        // 随时更新最小的绝对值
        min_abs = std::min(min_abs, abs_val);
    }

    // 这里就是我们上面分析的逻辑啦！
    // 如果负数个数是偶数，或者数组里有0
    if (neg_count % 2 == 0 || has_zero) {
        // 那么所有数都能变成非负数，最大和就是绝对值之和
        std::cout << total_sum << "\n";
    } else {
        // 否则，必须留下一个负数，我们留下绝对值最小的那个
        // 从绝对值总和里减去两倍的最小绝对值
        std::cout << total_sum - 2 * min_abs << "\n";
    }
}

int main() {
    // 这两行是为了让输入输出快一点，对付大数据量很有用！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题最核心的知识点就是 不变量 (Invariant) 的思想。

什么是不变量呢？ 不变量是指在执行一系列操作的过程中，某个属性或数量始终保持不变。就像这道题里，无论我们怎么翻转相邻的数对，负数个数的奇偶性这个属性是不会变的（除非有0这个“作弊器”）。

为什么不变量这么重要？ 在算法问题中，操作可能千变万化，状态空间非常大。如果我们能找到一个不变量，就等于给这个复杂的问题找到了一个约束和规律。这可以大大简化我们的分析过程。

• 简化问题：它能帮我们排除掉大量不可能达到的状态。比如这道题，我们知道了奇偶性不变，就不用去想怎么把奇数个负数变成0个负数了，因为那根本做不到。
• 指明方向：不变量可以引导我们走向正确的解题策略。知道了最终状态必须和初始状态有相同的“奇偶性”，我们就能确定最终的最优状态是什么样的（0个负数或1个负数）。

寻找不变量是解决很多构造题、博弈论和思维题的法宝。下次遇到类似的问题，主人可以试着从操作入手，看看有没有什么东西是“变来变去，但总有些东西不变”的，说不定就能找到解题的钥匙啦！🔑

好啦，这次的讲解就到这里了，希望主人能够喜欢！如果还有不懂的，随时可以再来问本喵哦！喵~ 💖