在 Python 中查詢從陣列中刪除元素可以獲得的最大點數

假設我們有一個包含 N 個元素的陣列 A，我們還有兩個整數 l 和 r，其中 1≤ ax ≤ 10^5 且 1≤ l≤ r≤ N。從陣列中取一個元素，例如 ax 並將其刪除，同時還刪除陣列中等於 ax+1、ax+2 … ax+R 和 ax-1、ax-2 … ax-L 的所有元素。這樣做將花費 ax 點。我們必須最大化刪除陣列中所有元素後的總成本。

因此，如果輸入類似於 A = [2,4,3,10,5]，l = 1，r = 2，則輸出將為 18。

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

  • n := 陣列的大小

  • max_val := 0

  • 對於 i 從 0 到 n，執行以下操作：

    • max_val := max_val 和 array[i] 中的最大值

  • count_list := 一個大小為 (max_val + 1) 的陣列，填充為 0

  • 對於 i 從 0 到 n，執行以下操作：

    • count_list[array[i]] := count_list[array[i]] + 1

  • res := 一個大小為 (max_val + 1) 的陣列，填充為 0

  • res[0] := 0

  • left := left 和 right 中的最小值

  • 對於 num 從 1 到 max_val + 1，執行以下操作：

    • k := num - left - 1 和 0 中的最大值

    • res[num] := res[num - 1]、num * count_list[num] + res[k] 中的最大值

  • 返回 res[max_val]

示例

讓我們看看以下實現以更好地理解：

 即時演示

def get_max_cost(array, left, right) :
   n = len(array)
   max_val = 0
   for i in range(n) :
      max_val = max(max_val, array[i])
   count_list = [0] * (max_val + 1)
   for i in range(n) :
      count_list[array[i]] += 1
   res = [0] * (max_val + 1)
   res[0] = 0
   left = min(left, right)
   for num in range(1, max_val + 1) :
      k = max(num - left - 1, 0)
      res[num] = max(res[num - 1], num * count_list[num] + res[k])
   return res[max_val]
array = [2,4,3,10,5]
left = 1
right = 2
print(get_max_cost(array, left, right))

輸入

[2,4,3,10,5] , 1, 2

輸出

18

更新於: 2020年8月25日

230 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

立即開始
廣告