Python 中陣列 K 次取反後最大和

假設我們有一個整數陣列 A，我們需要按照以下方式修改陣列：

我們可以選擇一個索引 i 並將 A[i] 替換為 -A[i]，並且我們將重複此過程 K 次。我們需要返回透過這種方式更改陣列後陣列的最大可能總和。

因此，如果陣列 A = [4,2,3]，並且 K = 1，則輸出將為 5。因此，選擇索引 1，陣列將變為 [4,-2,3]

為了解決這個問題，我們將遵循以下步驟：

• 對陣列 A 進行排序

• 對於 i 從 0 到 A 的長度 - 1

  • 如果 A[i] < 0，則 A[i] := - A[i]，並將 k 減 1

  • 如果 k = 0，則退出迴圈

• 如果 k 為偶數，則

  • sp := A[0]

  • 對於 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

Arnab Chakraborty

更新於: 2020年4月27日

280 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習