考虑两堆相邻但奇妙值符号相反的石子(0既可以视为正也可以视为负)，无论合并时是谁减谁，新石子堆的奇妙值绝对值都等于原石子堆奇妙值绝对值之和，而谁减谁可以决定新石子堆的符号，那就不难构造一种顺序，使得每次合并都是在操作两堆奇妙值符号相反的石子，而最后一次合并奇妙值一定是一正一负，此时用正奇妙值减负奇妙值，那么最终答案就是所有奇妙值的绝对值之和。
注意一些特殊情况的处理，例如奇妙值全为正或全为负的时候，必须牺牲一部分绝对值之和，先选择一个两堆石子合并来得到一个不同的符号，此外n=1的时候又不适用于全正全负的处理，都是需要注意的点。

std

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#define MAXN 2000005
#define Abs(x) (((x)>0)?(x):(-(x)))
using namespace std;
inline int read()
{
    int num=0,sgn=1;
    char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if (ch=='-')sgn=-1,ch=getchar();
    while (ch>='0'&&ch<='9')num*=10,num+=ch-'0',ch=getchar();
    return num*sgn;
}
int T,n,s[MAXN];
int pos,neg,ans,mn;
int main(){
    T=read();
    while (T--)
    {
        n=read();
        pos=neg=ans=0;
        for (int i=1;i<=n;i++)
        {
            s[i]=read();
            if (s[i]>=0)pos=1;
            if (s[i]<=0)neg=1;
            ans+=Abs(s[i]);
        }
        if (n==1)
        {
            printf("%d\n",s[1]);
            continue;
        }
        mn=ans;
        for (int i=2;i<=n;i++)
            mn=min(mn,Abs(s[i])+Abs(s[i-1])-Abs(s[i]-s[i-1]));
        if (pos*neg)printf("%d\n",ans);
        else printf("%d\n",ans-mn);
    }
    return 0;
}