PythonでK否定後の配列の合計を最大化する

整数の配列Aがあるとすると、次の方法で配列を変更する必要があります-

iを選択してA[i]を-A[i]に置き換えることができ、このプロセスをK回繰り返します。このように変更した後、配列の可能な最大の合計を返す必要があります。

したがって、配列A =[4,2,3]、K =1の場合、出力は5になります。したがって、インデックス1を選択すると、配列は[4、-2,3]

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

• 配列Aを並べ替える

• 0からA–1の長さの範囲のiの場合

  • A [i] <0の場合、A [i]：=--A [i]であり、kを1減らします

  • k =0の場合、ループから抜けます

• kが偶数の場合、

  • sp：=A [0]

  • for i：=1からAの長さ– 1

    • A [i]> 0の場合、sp：=spとA[i]

      の最小値

  • Aの要素の合計を返す–（2 * sp）

• それ以外の場合は、A

  の要素の合計を返します

例（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