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

  • Z时代
  • 2024-01-10
  • 分类：综合

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

以上是 查找可以通过在Python中删除数组中的元素获得的最大点数 的全部内容， 来源链接： utcz.com/z/347426.html

回到顶部