1. 根据a[i - 1] += a[i], a[i] -= 2 * a[i], a[i + 1] += a[i], 每次操作a[i]便只交换s[i]和s[i - 1], 故s[0]和s[n]位置不变

2. 重复走的路线尽可能的短

3. 若s[0] > s[n]，在曲线两端数值处于s[n],s[0]之间的点在经过排序后会被归到中间段的曲线内，差值会更小，那么此时取s0 = s[n]，sn = s[0]，重复走的路线则变短了（少了原来左边s[0]->s[n]'以及右边s[0]'->s[n]的路线，一撇表示数值相同) 。若s[n] > s[0]，则取s0 = s[0], sn = s[n]。最终路线为s0->最小值->最大值->sn。

4. 考虑1, 2, 3, 4四个点，有2->4, 3->1, 若2->4不是最优的，则会变为2->3, 4->1, 而4->1显然大于2->4, 故应该隔一个跳一个

Python3 代码

T = int(input())
for _ in range(T):
    n = int(input())
    s = [0] * (n + 1)  # 存放前缀和
    st = [False] * (n + 1)  # 保存状态
    a = [0]  # 初始值
    a.extend(list(map(int, input().split())))
    f = [0] * (n + 1)  # 最终状态

    # 构造前缀和
    for i in range(1, n + 1):
        s[i] = s[i - 1] + a[i]

    # s0取小值
    if s[0] < s[-1]:
        s0, sn = s[0], s[-1]
    else:
        s0, sn = s[-1], s[0]

    s.sort()
    s0, sn = s.index(s0), s.index(sn)

    l, r = 0, n
    for i in range(s0, -1, -2):
        f[l], st[i] = s[i], True
        l += 1

    for i in range(sn, n + 1, 2):
        f[r], st[i] = s[i], True
        r -= 1

    for i in range(n + 1):
        if not st[i]:
            f[l] = s[i]
            l += 1

    res = 0
    for i in range(1, n + 1):
        res = max(res, abs(f[i] - f[i - 1]))

    print(res)