在 Python 中查找通过从数组中删除元素可以获得的最大点数

pythonserver side programmingprogramming更新于 2025/10/10 17:48:17

假设我们有一个包含 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

  • 对于范围为 0 到 n 的 i,执行

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

  • count_list := 大小为 (max_val + 1) 的数组,用 0 填充

  • 对于范围为 0 到 n 的 i,执行

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

  • res := 大小为 (max_val + 1) 的数组,用 0 填充

  • res[0] := 0

  • left := 左、右的最小值

  • 对于 1 到 max_val + 1 范围内的数字,执行

    • k := num 的最大值 - 左 - 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

相关文章


有用资源