Pythonで最大k回の符号反転操作を行い配列の合計を最大化する方法

リスト nums と整数 k が与えられたとします。ここで考える操作とは、nums から要素を1つ選び、その符号を反転させるものです。この操作をちょうど k 回実行したとき、得られる合計値の最大値を求めます。

例えば、入力が nums = [2, 1, -6, -2]、k = 3 の場合、出力は 9 になります。-6、-2、そして 1 の符号を反転すると [2, -1, 6, 2] となり、その合計は 9 になるためです。

解法のアプローチ

この問題は「貪欲法」を使って効率的に解くことができます。手順は以下の通りです。

• n を nums のサイズとします。
• n が 0 の場合は 0 を返します。
• リスト nums を昇順にソートします。
• idx を 0 から n - 1 までループします。
  • nums[idx] が負の値で、かつ k が 0 より大きい場合：
    • k を 1 減らします。
    • nums[idx] の符号を反転します。
• k が奇数の場合：(nums の全要素の合計) − (2 × nums の最小値) を返します。
• それ以外の場合は、nums の全要素の合計を返します。

アルゴリズムのポイント

• まずソートを行うことで、最も小さい（負の）要素から優先的に符号を反転できます。負の数を正に変えると合計が増えるため、これは常に有利です。
• すべての負の数を反転しても操作回数が残っている場合、残りが偶数回であれば、同じ要素を2回反転して元に戻せるため合計は変わりません。
• 残りが奇数回の場合は、どこか1つの要素を余分に反転する必要があります。影響を最小限に抑えるには最小値を選ぶのが最適で、最小値 x を反転すると合計は sum − 2x だけ減少するため、「合計 − 2 × 最小値」を返せばよいのです。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(nums, k):
    n = len(nums)
    if n == 0:
        return 0

    nums.sort()
    for idx in range(n):
        if nums[idx] < 0 and k > 0:
            k -= 1
            nums[idx] *= -1

    if k & 1 == 1:
        return sum(nums) - 2 * min(nums)

    return sum(nums)

nums = [2, 1, -6, -2]
k = 3
print(solve(nums, k))

入力

[2, 1, -6, -2], 3

出力

9