<分区>
我正在阅读“Introduction to Algorithms: A Creative Approach”并在第 1 章中遇到了这个问题:
Problem 1.3: You have a list of numbers, erase as few numbers as possible to make remaining numbers in increasing order.
例如给定数组
9 44 32 12 7 42 34 92
两个可能的选项是 9 12 42 92 和 32 42 92，前者删除的数字较少。
我尝试了一个递归算法但对它的性能不满意，因为它仍然需要测试太多的组合。我找到了一种启发式算法，可以快速得到好的结果，虽然我不确定它是否能保证最好的结果。我在网上搜索但没有找到关于这个问题的任何讨论。我相信应该有更好的算法。
我写了我的 2 个方法 here以备不时之需。
更新:我在询问这个问题的解决方案，@josilber 和@templatetypedef 给出了链接和正确的查看方向。事实证明，这是具有良好解决方案的一系列已知问题的特例。这里不用写详细的解法，Longest increasing subsequence, Patience sorting 的wiki页面提供了详细的信息。
值得注意的是，虽然答案中有一些链接，但这个问题并不是要资源或链接。真正的答案是“这个问题是一些已知已解决问题的变体”的知识。