与えられた数列 \(A\) を並び替えたときに \(\sum_{i=1}^{N-1}|A_i-A_{i+1}|\) としてありえる最大値を求める問題です。

この上の式を\(A_i\) と \(A_{i+1}\) の大小比較によって適切に展開し、その時の書く \(A_i\) の係数を考えます。

例えば、\(A=(3,1,2)\) のとき、\(|A_1-A_2|+|A_2-A_3|=A_1-A_2-A_2+A_3\) で、\(A_1,A_2,A_3\) の係数はそれぞれ \(1,-2,1\) です。

\(A_1,A_N\) の係数は \(1\) または \(-1\) でその他の要素の係数は \(2,0,-2\) のいずれかです。 また、係数の総和は必ず \(0\) になります。

\(N\) の偶奇で場合分けしてこの係数を適切に決めて最大化することを考えます。

また、以降 \(A\) を昇順に並べ替えた列を \(B\) とします。

\(N\) が偶数の場合

\(N=2m\) とします。

実は \(B_1,B_2,\ldots,B_{m-1}\) の係数を \(-2\) 、\(B_{m+2},\ldots,B_N\) の係数を \(2\) 、\(B_{m}\) の係数を \(-1\) 、\(B_{m+1}\) の係数を \(1\) とすることで最大を達成できます。

\(B_{i+1}-B_i\) の寄与を考えると上界がこの値であることが言えて証明できます。

実際の並びは\(A_1=B_{m+1},A_N=B_{m}\) とし、\(A_{2k+1}\) には\(B_{m+2},\ldots,B_N\) を、\(A_{2k}\) には \(B_1,B_2,\ldots,B_{m-1}\) を入れればよいです。

つまり、答えは\(2\times (\sum_{i=m+1}^{N}B_i-\sum_{i=1}^{m}B_i)- B_{m+1}+B_m\) となります。

\(N\) が奇数の場合

\(N=2m+1\) とします。

偶数の場合と同じように係数を考えます。

• \(B_1,B_2,\ldots,B_{m-1}\) の係数を\(-2\) 、\(B_m,B_{m+1}\) の係数を \(-1\) 、\(B_{m+2},\ldots,B_{2m+1}\) の係数を \(2\) とする。
• \(B_1,B_2,\ldots,B_m\) の係数を \(-2\)、\(B_{m+1},B_{m+2}\) の係数を \(1\) 、\(B_{m+3},\ldots,B_{2m+1}\) の係数を \(2\) とする。

のどちらかが最適となります。 それぞれ、小大小大小…大小、大小大小…小大として適切に係数が\(-1,1\) のものを配置することで達成できます。

つまり答えは\(2\times (\sum_{i=m+2}^{2m+1}B_i-\sum_{i=1}^{m}B_i)-\min(B_{m+1}-B_m,B_{m+2}-B_{m+1})\) となります。

証明は\(N\) が偶数の場合と似たように \(B\) の差分を見ることで上界であることを示せます。

実装の際は\(N=1\) に注意する必要があります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& e : a) cin >> e;
    sort(a.begin(), a.end());
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }
    if (n % 2 == 0) {
        long long ans = 0;
        for (int i = 0; i < n / 2; ++i) ans -= 2 * a[i];
        for (int i = n / 2; i < n; ++i) ans += 2 * a[i];
        ans -= a[n / 2];
        ans += a[n / 2 - 1];
        cout << ans << endl;
    } else {
        long long ans = 0;
        for (int i = 0; i < n / 2; ++i) ans -= 2 * a[i];
        for (int i = n / 2 + 1; i < n; ++i) ans += 2 * a[i];
        ans -= min(a[n / 2 + 1] - a[n / 2], a[n / 2] - a[n / 2 - 1]);
        cout << ans << endl;
    }
}