我有一个整数序列 {a1,a2...an}，我想将它分成最少的“递增子序列”。例如：假设序列为{10,30,20,40}，那么答案应该是2。在这种情况下，第一个递增序列将是{10,30,40}，第二个递增序列将是{20}。我能够使用O(N^2)算法来完成，但我特别希望有一个O(N*logN)的解决方案可以达到同样的效果。
最小递增子序列数量
4
- divanshu
3
分割序列的条件是什么？我不明白为什么{10,30,20,40}应该被准确地分割成这样，而不是其他东西。 - lenz
最小的数字不是零吗？除非它已经排序。 - Novak
对不起，我漏掉了最关键的单词 - “增加”。我已经编辑了问题。现在已经修复了。 - divanshu
1个回答
6
这可以使用简单的贪心算法完成。
保持已发现的子序列的排序数组。按照每个序列中最后一个整数的值按递减顺序排序。初始为空。
从序列中获取第一个尚未处理的元素，找到最后一个整数小于此元素但大于（或等于）所有此类子序列中的整数的子序列。在此处使用二分搜索以获得总体复杂度O（N log N）。如果找不到这样的子序列，则在数组末尾添加一个新的子序列。将此元素添加到此子序列中。重复操作，直到序列中还有未处理的元素。
- Evgeny Kluev
4
一个已排序的子序列数组？我相信在最坏的情况下可能有2^n个这样的子序列？ - divanshu
@divanshu：不，最坏情况下，当原始序列按降序排序时，恰好有N个长度为1的子序列。 - Evgeny Kluev
2+1：也许值得补充一下，这个问题被称为“耐心排序”。 - Peter de Rivaz
谢谢@PeterdeRivaz！你提出的“耐心排序”这个术语帮了我很多。 - divanshu
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接