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