在 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 的元素。这样做会损失 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

