Pythonで最大k個の否定演算を実行して最大合計を見つけるプログラム

numsという要素のリストがあり、別の値kもあるとします。ここで、numsから要素を選択してそれを否定する操作について考えてみましょう。正確にk個の操作を実行できます。生成できる最大の結果の合計を見つける必要があります。

したがって、入力がnums =[2、1、-6、-2] k =3のような場合、-6と-2を否定すると、出力は9になり、1は[2、-1、6 、2]そしてその合計は9です。

これを解決するには、次の手順に従います-

• n：=numsのサイズ

• nが0と同じ場合、

  • 0を返す

• リスト番号を並べ替える

• 0からn-1の範囲のidxの場合、実行

  • nums [idx]<0かつk>0の場合、

    • k：=k-1

    • nums [idx]：=-nums [idx]

• kが奇数の場合、

  • return（numsに存在するすべての要素の合計）-（2 * numsの最小値）

• numsに存在するすべての要素の合計を返す

例

理解を深めるために、次の実装を見てみましょう

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