\(N\) が偶数の場合を考えます。

隣接するという条件をなくし、数列の任意の \(2\) 要素を選びどちらも数列から削除するとしたとき、得られるスコアの合計としてありうる最大値は、\(A\) の要素のうち大きい方 \(\frac{N}{2}\) 個の総和から、小さい方 \(\frac{N}{2}\) 個の総和を引いたものです。

隣接するという条件を加えても、この理論値を達成することができます。

具体的には、\(A\) の要素のうち大きい方 \(\frac{N}{2}\) 個を + で、小さい方 \(\frac{N}{2}\) 個を - で置き換えて得られる文字列を考えます。 例えば、\(A=(3,1,4,1,5,9)\) のとき、\(S\) は --+-++ です。 - と + がどちらも \(1\) つ以上含まれる文字列において必ず - と + が隣接する箇所があるので、\(S\) に対して隣接する - と + のペアを削除することを \(\frac{N}{2}\) 回繰り返すことが可能です。

次に、\(N\) が奇数の場合を考えます。

最後に残る \(1\) つの要素を決め打ちます。 その要素で数列を左右に分割したとき、左右の数列はどちらも長さが偶数となる必要があるので、最後に残る \(1\) つの要素としてありうるものは \(A_1, A_3, A_5, \ldots, A_N\) です。 それぞれに対して、左右に分割された偶数長の数列それぞれの、大きい方半分の総和から小さい方半分の総和を引いた値を高速に求める必要があります。これは、集合への値の追加と集合の中央値の管理ができるデータ構造を応用することで実現できます。 例えば、優先度付きキューを \(2\) つ使う方法や、BIT を使う方法があります。

計算量は \(O(N\log N)\) です。