我有一个整数序列 {a1,a2...an},我想将它分成最少的“递增子序列”。例如:假设序列为{10,30,20,40},那么答案应该是2。在这种情况下,第一个递增序列将是{10,30,40},第二个递增序列将是{20}。我能够使用O(N^2)算法来完成,但我特别希望有一个O(N*logN)的解决方案可以达到同样的效果。
我有一个整数序列 {a1,a2...an},我想将它分成最少的“递增子序列”。例如:假设序列为{10,30,20,40},那么答案应该是2。在这种情况下,第一个递增序列将是{10,30,40},第二个递增序列将是{20}。我能够使用O(N^2)算法来完成,但我特别希望有一个O(N*logN)的解决方案可以达到同样的效果。
这可以使用简单的贪心算法完成。
保持已发现的子序列的排序数组。按照每个序列中最后一个整数的值按递减顺序排序。初始为空。
从序列中获取第一个尚未处理的元素,找到最后一个整数小于此元素但大于(或等于)所有此类子序列中的整数的子序列。在此处使用二分搜索以获得总体复杂度O(N log N)。如果找不到这样的子序列,则在数组末尾添加一个新的子序列。将此元素添加到此子序列中。重复操作,直到序列中还有未处理的元素。