查找可以通过在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