\(\{ A_i \}\) を \(0\) より大きい数からなる数列 \(\{ B_i \}\) と \(0\) より小さい数からなる数列 \(\{ C_i \}\) と \(0\) からなる数列 \(\{ D_i \}\) に分割する.

戦略は3つある.

(1) 結果を正にできるので, 符号が同じで絶対値が大きいもの同士を掛ける

(2) 0を掛ける要素に入れる

(3) 結果が負にしかなりえないので, 符号が同じで絶対値が小さいもの同士を掛ける

この戦略を上から順に試して採用できるかを判断していく.

(1) を採用する場合

\(K\) が奇数の場合は \(\{ B_i \}\) から最初1つ取り出す. \(K\) が偶数の場合は取り出さない.

その後, \(\{ B_i \}, \{ C_i \}\) から積の絶対値が大きい方の2つを取り出していく. 取り出しきれたらそれでOKである.

(2) を採用する場合

\(\{ D_i \} \neq \varnothing\) なら結果を \(0\) にできる.

(3) を採用する場合

\(\{ B_i \}, \{ C_i \}\) から絶対値が小さいものを順に取り出していく.