x********o
发帖数: 519 | 1 一个任意的数组，找出一个严格单调递增的最长子序列。
例如: {3,0,1,7,2,4,5,9} –> output： {0, 1, 2, 4, 5, 9} | h*********n
发帖数: 11319 | 2 LCS("3,0,1,7,2,4,5,9", "0,1,2,3,4,5,7,9")
【在 x********o 的大作中提到】
: 一个任意的数组，找出一个严格单调递增的最长子序列。
: 例如: {3,0,1,7,2,4,5,9} –> output： {0, 1, 2, 4, 5, 9}
| l*****a
发帖数: 559 | 3 or search LIS for a nlog(n) solution
【在 h*********n 的大作中提到】
: LCS("3,0,1,7,2,4,5,9", "0,1,2,3,4,5,7,9")
| k****n
发帖数: 369 | 4 经典题，用一个栈，每个新数都退栈到比它小的。
只想知道最大长度的话，保存迄今最大长度就够了
还想知道序列的话，需要在当前是最大长度而且需要pop的时候把栈clone下来
【在 x********o 的大作中提到】
: 一个任意的数组，找出一个严格单调递增的最长子序列。
: 例如: {3,0,1,7,2,4,5,9} –> output： {0, 1, 2, 4, 5, 9}
| h*********n
发帖数: 11319 | 5 能详细讲讲么？
【在 k****n 的大作中提到】
: 经典题，用一个栈，每个新数都退栈到比它小的。
: 只想知道最大长度的话，保存迄今最大长度就够了
: 还想知道序列的话，需要在当前是最大长度而且需要pop的时候把栈clone下来
| d*******l
发帖数: 338 | | i**********e
发帖数: 1145 | 7 LIS 经典题嘛，之前个礼拜不就有人问过了吗？
有 O(N^2) 的 DP，还有 O( N log N） binary search 的解法。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | y***n
发帖数: 1594 | | i**********e
发帖数: 1145 | 9 LZ，建议你这本书：
The Algorithm Design Manual by Steven. Skiena
里面的第三DP章节就有介绍这题的解法。
解释的非常好，强烈推荐。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 x********o 的大作中提到】
: 一个任意的数组，找出一个严格单调递增的最长子序列。
: 例如: {3,0,1,7,2,4,5,9} –> output： {0, 1, 2, 4, 5, 9}
|
|
