p*******o
发帖数: 3564 | 1 www.careercup.com/question?id=11978701f
Given an array of integers, find the longest subsequence of elements which
monotonically increases. for ex. array = {1 4 8 2 5 7 3 4 6}, the longest
subsequence = {1 2 3 4 6}
I have explained him about O(N^2) with O(1) space algorithm but the
interview is expecting O(N log N). Could any one help me explaining the
algorithm in detail ? |
q******8
发帖数: 848 | 2 我觉得这么问确实挺没劲的，没见过这个nlogn解法的，当场想出来的，岂不是高德纳
了。 |
b***e
发帖数: 383 | |
f*******t
发帖数: 7549 | 4 这个算法课都学过的吧，其实挺基本的，当然我也不会…… |
n*******w
发帖数: 687 | 5 这个挺详细。
二分查找加上两个辅助数组。
【在 b***e 的大作中提到】
: http://www.felix021.com/blog/read.php?1587
: 这是我见过的写得最清楚的一篇文章。
|
d*********i
发帖数: 628 | 6 DP吧，我记得是O(nlogn)
也是算法课上面讲过... |
a****h
发帖数: 126 | 7 这个好像有问题吧。
【在 b***e 的大作中提到】
: http://www.felix021.com/blog/read.php?1587
: 这是我见过的写得最清楚的一篇文章。
|
