0

考虑以下数字：

9,44,32,12,7,45,31,98,35,37,41,8,20,27,83,64,61,28,39,93,29,92,17,13,14, 55,21,66,72,23,73,99,1,2,88,77,3,65,83,84,62,5,11,74,68,76,78,67,75,69, 70、22、71、24、25、26。

我尝试实现一种算法来删除列表中最少数量的数字来制作序列

a) 递增顺序 b) 递减顺序

我已经尝试过最短和最长的子序列。不想要代码，只想要解释或伪代码，我不明白如何解决问题谢谢！

4

2 回答 2

2

这是一个轻微伪装的最长增加（减少）子序列问题。解决您的问题的算法如下：

  • 查找数组中最长的递增（递减）子序列
  • 删除所有不属于最长递增子序列的元素。

由于递增/递减子序列最长，因此您将删除的数字量是最小的。

维基百科文章有一个很好的伪代码来解决 LIS/LDS 问题。除非原始序列的长度超过 1000 个元素，否则您可以用二分搜索代替线性搜索。

于 2013-08-15T01:41:20.123 回答
0

既然已经提到过，我将添加我的 2 美分。在这种情况下，很可能会在面试中被问到，运行时间（效率）是一个主要问题。因此，根据执行时间的不同，可以使用许多算法来解决相同的问题。最著名的算法是 O(nlogn) 阶。其他重要的可以像动态编程范式也可以应用于产生 O(n^2) 的解决方案。

O(n^2) 这里

O(nlogn) 这里

于 2013-08-16T13:27:05.493 回答