5 隣接積和が最大となる並び

まずは $S_3$, $S_2$ を最大にする並びの方を考える。

補題 1.

$x$,$y$ を、 $x\leq y\leq a_1$ であるとする。 $a_1,a_2,\ldots,a_k$ ( $a_1\leq a_2\leq\cdots\leq a_k$) の 並べかえ $A$ の左端が $a_1$ でない場合、 $A'=[a_1 \cdots]$ の形の $A$ の並べかえで、

$$S_3([x A y])\leq S_3([x A' y])$$

となるものが存在する。

この補題は、列の両端にその最小のものを配置したような 並びのうちの $S_3$ の最大値を考えた場合、 その両端以外の最小要素 $a_1$ が、列全体の最小要素 $x$ と 隣接しないものよりは隣接するものの方が大きくなる (厳密にはそれ以上になる) ことを示していて、 よって最大値もそのような形の並びの中にあることになる。

この補題 1 は、反転列を用いて構成的に証明するが、 その手法はこの後も用いる。今回は少し丁寧に説明する。

証明

$A$ は $a_1$ を左端に持たないので、

$$[A y]= [B a_1 C]$$

のように書くことができ、この $B$ の左端を $p$、 $C$ の左端を $q$ とする:

$$B=[p \cdots],\hspace{1zw}C=[q \cdots y]$$

仮定より $n(B)\geq 1$ であるが、$C$ は $[y]$ のみの場合もありうる。 その場合は $q=y$ と考える。このとき、

$$[x A y] =[x B a_1 C] =\left[x \fbox{$p \cdots$} a_1 \fbox{$q \cdots y$}\right]$$ (10)

となっている。これに対し、 $A$ の $[B a_1]$ の部分をまとめて逆順にしたものを $A'$ とする。 このとき、

$$[x A' y] = [x a_1 \bar{B} C] = \left[x a_1 \fbox{$\cdots p$} \fbox{$q \cdots y$}\right]$$ (11)

となる。これらに対し、 $S_3([x A y])$ と $S_3([x A' y])$ の 値を比較する。

これらの列の違いは、 $[B a_1]=[p \cdots a_1]$ の部分が 逆転しているところで、 その部分に対する $S_3$ の値と、$C$ の部分に対する $S_3$ の値は 両者で共通である ( $S_3([B a_1])=S_3([a_1 \bar{B}])$)。

よって、 $S_3([x A y])$ と $S_3([x A' y])$ の違いは、 その境界部分だけであり、その項は、 $S_3([x A y])$ の方は (10) より $xp$ ($x$ と $A$ の境界) と $a_1q$ ($a_1$ と $C$ の境界)、 $S_3([x A' y])$ の方は (11) より $xa_1$ と $pq$ ($\bar{B}$ と $C$ の境界) となる。 よって、

$$S_3([x A y])-S_3([x A' y]) = xp+a_1q-xa_1-pq = (x-q)(p-a_1)$$ (12)

となる。ここで、$q$ は $a_2,\ldots,a_k$ か $y$ のいずれかなので、 仮定より $q\geq y\geq x$ であり、 また $p$ は $a_2,\ldots,a_k$ のいずれかなので $p\geq a_2\geq a_1$ である。 よって (12) の右辺は 0 以下となり、 $S_3([x A y])\leq S_3([x A' y])$ となる。

これは、例えば

$$S_3\left(\left[1 \fbox{4 5 3} 2\right]\right) \leq S_3\l... ...\right) \leq S_3\left(\left[1 \fbox{3 4} 5 2\right]\right)$$

のように、それぞれ左辺に対して $S_3$ がそれ以上の値となるような 並べかえがあることを示している。

この補題 1 を使えば $S_3$, $S_2$ の最大値を与える 並びを決定することができる。 まず $S_3$ を考える。

$a_1,\ldots,a_n$ の並べかえ $A$ に対し、列 $[0 A 0]$ を考えると、 $S_3([0 A 0])=S_3(A)$ で、 $a_1\geq 0$ より補題 1 を適用でき、 $S_3(A)=S_3([0 A 0])$ を最大にするには $a_1$ は $A$ の左端 (または右端) に置く方が良いことがわかる。

よって $A=[a_1 A']$ とし、次は列 $[A 0]=[a_1 A' 0]$ を考える。

$$S_3(A) = S_3([A 0]) = S_3([a_1 A' 0]) = S_3([0 \bar{A'} a_1])$$

と見ると、$0\leq a_1$ で $\bar{A'}$ の要素はすべて $a_1$ 以上なので、 補題 1 よりそれを最大にするには、 $\bar{A'}$ の最小要素はその左端 ($A'$ では右端) に置く方がよい。 これにより、 $A=[a_1 A'' a_2]$ となる。

以下同様にして (この後は 0 は追加しなくてよい)、 $A''$ の左端が $a_3$、右端が $a_4$、と 端からジグザグ順に小さいものを並べるときに大きくなることになり、 最終的に $S_3$ の最大値を与える並びは、

$$A = [a_1 a_3 a_5 \cdots a_6 a_4 a_2]$$ (13)

のようになる。

次は、$S_2$ を考える。これは巡回的なので、 左端は任意の $a_j$ に固定して考えればよいので、それを $a_1$ とし、 $A=[a_1 A']$ とする。このとき、

$$S_2(A) = S_2([a_1 A']) = S_3([a_1 A' a_1]) = S_3([a_1 \bar{A'} a_1])$$ (14)

と、$S_2(A)$ を $S_3$ で表現できる。 よって上の $S_3$ に対する結果により、 $A'$ は $a_2,\ldots,a_n$ を右端から (左端からでもよい) 小さい順に ジグザグに並べていけばよいことがわかる。 $A$ はその左端に $a_1$ を追加したものだから、 結局その $A$ は (13) と同じものになる。 よって、$S_2$ の最大値もこの並びにより与えられることになる。

定理 2.

$S_2(A)$, $S_3(A)$ は、 (13) の並びのときにいずれも最大となる。 並べ方はいずれも左端からジグザグ順に並べていく。

なお、最大値を与える並びは一意には決まらない。 左右を反転させたものや、$S_2$ の場合にはそれを 巡回的にずらしたものももちろん最大値を与えるが、 それだけではない。

例えば、 $A = [1 2 3 3 4 5]$ の場合には、 最大を与える並び (13) は、 $[1 3 4 5 3 2]$ となるが、3 が 2 つ入っているため、 そこから先 (内側) は左右のジグザグ順を逆にしても $S_3$ は同じ値になる:

$$S_3([1 3 4 5 3 2]) = S_3([1 3 5 4 3 2])$$

このように、数列の中に同じ値の要素が含まれている場合は、 最大値を与える並びかえのバリエーションが色々できてしまう。