我有一个整数序列 {a1,a2...an}，我想将它分成最小数量的“递增子序列”。例如:令序列为{10,30,20,40}，则答案为2。在这种情况下，第一个递增序列为{10,30,40}，第二个为{20}。我可以使用 O(N^2) 算法来完成此操作，但我对可以达到此目的的 O(N*logN) 解决方案特别感兴趣。
最佳答案
这可以通过简单的贪心算法来完成。
保留到目前为止找到的子序列的排序数组。按每个序列中最后一个整数的值降序排序。最初为空。
从序列中获取第一个尚未处理的元素，并找到最后一个整数小于此元素但大于(或等于)所有此类子序列的子序列。在这里使用二进制搜索来获得整体复杂度 O(N log N)。如果没有找到这样的子序列，则在数组末尾添加一个新的。将此元素添加到此子序列。当序列中有未处理的元素时重复。
关于algorithm - 递增子序列的最小数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17023502/