PythonでK回の符号反転後に配列の合計を最大化する

問題概要

整数の配列 A が与えられます。この配列に対して、次の操作をちょうど K 回行うことを考えます。

• 任意のインデックス i を選び、A[i] を -A[i] に置き換える(符号を反転する)

すべての操作を行ったあとの配列の合計として、考えられる最大値を求めるのがこの問題です。

例: A = [4, 2, 3]、K = 1 の場合、出力は 5 になります。インデックス 1 を選んで反転すると配列は [4, -2, 3] となり、合計は 4 + (-2) + 3 = 5 となるからです。

解法の考え方(貪欲法)

この問題は貪欲法で解くのが有効です。基本となる発想は次の通りです。

• 負の数が残っているうちは、それを優先的に正の数へ反転する(合計が必ず増えるため)
• 反転の回数が余った場合、同じ要素を2回反転すれば元に戻るので、残りが偶数回なら合計には影響しない
• 余りが奇数回のときは、どうしても1回分の反転が残るため、絶対値が最小の要素を1回だけ反転して損失を最小限に抑える

アルゴリズムの手順

1. 配列 A を昇順にソートする
2. i を 0 から A の長さ - 1 まで順番に処理する:A[i] < 0 なら A[i] := -A[i] として残り回数 k を 1 減らし、k が 0 になったらループを抜ける
3. 残った k が奇数の場合:sp := A[0] とし、i を 1 から A の長さ - 1 まで走査して A[i] ≥ 0 なら sp := min(sp, A[i]) で更新する。最後に「配列の合計 − 2 × sp」を返す
4. 残った k が偶数の場合:そのまま配列の要素の合計を返す

「2 × sp」を引く理由は、最小要素 sp を1回反転すると合計がちょうど 2 × sp だけ減少するためです。絶対値が最小の要素を選べば、この減少量を最小化できます。

Pythonでの実装例

以下の実装を見ると、理解がより深まるでしょう。

class Solution(object):
   def largestSumAfterKNegations(self, A, K):
      A.sort()
      for i in range(len(A)):
         if A[i] < 0:
            A[i] = -A[i]
            K -= 1
         if K == 0:
            break
      if K % 2:
         smallest_positive = A[0]
         for i in range(1, len(A)):
            if A[i] >= 0:
               smallest_positive = min(smallest_positive, A[i])
         return sum(A) - (2 * smallest_positive)
      else:
         return sum(A)

ob1 = Solution()
print(ob1.largestSumAfterKNegations([3,-1,0,2],3))

入力

[3,-1,0,2]
3

出力

6

実行結果の解説

配列 [3, -1, 0, 2] をソートすると [-1, 0, 2, 3] になります。まず最小の負の数である -1 を反転して 1 とし、この時点で残り回数は 2 回です。残りが偶数なので、これ以上反転しても合計は増やせません(0 以外の要素を反転すると合計が減ってしまうだけです)。したがって答えは 1 + 0 + 2 + 3 = 6 となります。