algorithm - 如何在需要在它们之间有 k 个项目的序列中选择最大数量的项目？

Question

我正在学习算法，我经常会遇到这类问题。好的，我有一个数字列表，我必须找到这个列表的最大子列表，其中每个数字之间的距离等于或大于列表的大小。例如:

[1, 3, 5, 10]

本例中的距离是 4。那么，[1, 5, 10] 就是正确答案。请记住，当我删除数字 3 时，距离现在是 3。

任何直觉都会受到欢迎，我什至不知道如何解决这个问题。我尝试为每个数字生成可能的路径，例如 [1,5,9,13]，但我想不出一种方法来选择要删除的数字。这种问题声称可以在 O(N) 中解决。

Answer 1

解决方法很简单。

1. 首先计算初始列表 [1, 3, 5, 10] -> [2, ,2 , 5] 中连续数字之间的所有距离并记住长度。这是 O(n) 操作。
2. 请注意，然后您从初始列表中删除了数字，您只是将距离列表中的 2 个值相加，并将列表的长度减一。 s 这个观察导致了第二个贪婪的 O(n) 过程。您只需遍历距离列表并将它们与列表的当前长度进行比较。如果距离 >= 长度，则转到下一个元素。如果距离小于长度，则删除该元素(合并两个距离)并将长度减一并再次检查...

在每一步之后，您之前的所有距离 > 长度 > 新的减少长度。在程序结束时，您会得到想要的东西。