https://atcoder.jp/contests/abc173/submissions/21143239
- K個選んだときの積が負なら「負を1つ減らして正を1つ増やす」「正を1つ減らして負を1つ増やす」両方を試す必要がある
積を最大化するため、絶対値降順に貪欲にK個だけ選ぶ（実際に計算するとオーバーフローするため、選択するだけで計算はしない）。そのときの積合計が負になってしまうならK+1番目以降の負とK番目までの正を1組交換する。ただし、数列によってはK+1番目以降の正とK番目までの負を1組交換したほうが最善になる可能性がある。
具体的には つまり
なら正を1つ追加して負を1つ減らすという操作をし、逆なら逆の操作をするのが最善となる。2つの積ならオーバーフローしないので、ここだけ実際に計算して判断する。コーナーケースとして入力が全て負かつKが奇数なら絶対値昇順に貪欲にK個選ぶ。
実装するときは正と負を別に保存するdequeを用意するとシンプルになると思われる。
