dra*_*doc 4 arrays algorithm mathematical-optimization
我正在阅读"算法导论:创造性方法"并在第1章中遇到了这个问题:
问题1.3:您有一个数字列表,尽可能少地删除数字以使剩余数字按递增顺序排列.
例如,给定数组
9 44 32 12 7 42 34 92
两个可能的选项是9 12 42 92和32 42 92,前者删除的数字较少.
我尝试了一种递归算法,但对其性能不满意,因为它仍然需要测试太多的组合.我发现了一种可以快速获得良好结果的启发式算法,但我不确定它是否可以保证最佳结果.我在网上搜索但没有找到关于这个问题的任何讨论.我相信应该有一个更好的算法.
我在这里写了两个方法,以防你想检查.
更新:我问这个问题的解决方案,@ josilber和@templatetypedef提供了链接和正确的方向来查看.事实证明,这是一个具有良好解决方案的已知问题家族的特例.这里没有必要编写详细的解决方案,最长的子序列的维基页面,耐心排序提供了详细信息.
值得注意的是,虽然答案有一些链接,但这个问题并不是要求资源或链接.真正的答案是"这个问题是一些已知解决问题的变体"的知识.
作为提示,这相当于找到数组中增长最长的子序列(你知道为什么吗？)因为这是一个已知O(n log n)解决方案的标准算法,你应该能够通过稍加修改来解决问题LIS.
希望这可以帮助!