Cas*_*urr 0 c arrays algorithm sorted
我想在C中做一些事情,我需要一个算法,返回另一个数组中包含的最大维度明智的排序数组.所以,例如,如果我有以下数组:
A[5] = {5, 2, 3, 1, 4}
它应该返回:
2, 3, 4
我想不出任何有效的实施.有什么想法吗？谢谢.:)
pha*_*t0m 5
您的问题被称为" 增长最快的子序列 ".
这里可以找到利用动态编程的算法,并有一个很好的解释.它具有最优的渐近复杂度O(nlogn).
O(nlogn)
基本思想是,您可以跟踪具有长度的子序列的最佳可能最后元素(或者更确切地说是其索引)i.处理下一个元素时,检查数组m以查看是否有
i
m
归档时间：
13 年，3 月 前
查看次数：
683 次
最近记录：