数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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
对于 i 从 0 到 n，执行以下操作：
max_val := max_val 和 array[i] 中的最大值
count_list := 一个大小为 (max_val + 1) 的数组，填充为 0
对于 i 从 0 到 n，执行以下操作：
count_list[array[i]] := count_list[array[i]] + 1
res := 一个大小为 (max_val + 1) 的数组，填充为 0
res[0] := 0
left := left 和 right 中的最小值
对于 num 从 1 到 max_val + 1，执行以下操作：
k := num - left - 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
更新于: 2020年8月25日
230 次查看
广告