增加子序列的最小数量

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).如果没有找到这样的子序列,请在数组末尾添加一个新子序列.将此元素添加到此子序列中.重复执行序列中尚未处理的元素.