查找可以通过在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的元素。这样做将花费斧头点数。从数组中删除所有元素后，我们必须使总成本最大化。

因此，如果输入类似于A = [2,4,3,10,5]，l = 1，r = 2，则输出将为18。

为了解决这个问题，我们将遵循以下步骤-

• n：=数组大小

• max_val：= 0

• 对于0到n范围内的i，执行

• max_val：= max_val，数组[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

• 左：=左，右的最小值

• 对于1到max_val + 1范围内的num

• k：=最大值-左-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