algorithm - 删除元素以对数组进行排序

Question

我正在寻找一种算法来对数组进行排序，但不是通过移动值。相反，我想删除尽可能少的值并最终得到一个排序列表。基本上我想找到最长的升序子数组。

为了显示：

1 4 5 6 7 2 3 8

应该成为（2 删除）

1 4 5 6 7 8

而不是（5 次删除）

1 2 3

我可以看到如何以一种天真的方式做到这一点，即通过递归检查每个元素的“删除”和“不删除”树。我只是想知道是否有更快/更有效的方法来做到这一点。这类问题有通用的首选算法吗？

score 9 · Accepted Answer

您正在寻找最长的递增子序列问题。有一种算法可以在 O(n log n) 时间内解决它。

score 3 · Accepted Answer

该站点有一种 O(NlogN) 算法，它比递归算法更快。

2 回答 2