algorithm - 最小数量的递增子序列

Question

我有一个整数序列 {a1,a2...an} ，我想把它分成最小数量的“增加子序列”。例如：假设序列为 {10,30,20,40}，则答案为 2。在这种情况下，第一个递增序列为 {10,30,40}，第二个为 {20}。我可以使用 O(N^2) 算法来做到这一点，但我对可以达到目的的 O(N*logN) 解决方案特别感兴趣。

Answer 1

这可以通过简单的贪心算法来完成。

保持到目前为止找到的子序列的排序数组。按每个序列中最后一个整数的值按降序排序。最初是空的。

从序列中获取第一个尚未处理的元素，并找到最后一个整数小于此元素但大于（或等于）所有此类子序列的子序列。在这里使用二进制搜索来获得整体复杂度 O(N log N)。如果没有找到这样的子序列，则在数组末尾添加一个新子序列。将此元素添加到此子序列中。当序列中有尚未处理的元素时重复。