m*****n
发帖数: 5245 | 1 ☆─────────────────────────────────────☆
rentny2007 (rent) 于 (Sun Oct 25 15:15:53 2009, 美东) 提到:
比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
我的解法是sort this sequence X to Y, Get the LCS of X and Y.
Time = O(nlogn + n^2) = O(N^2)
对方说还能更快。谁知道该怎么改进？
Updated: 我忘了说了，是求*最长*单调上升子列
☆─────────────────────────────────────☆
algorithmics (沙盘推演) 于 (Sun Oct 25 15:19:28 2009, 美东) 提到:
求两个序列的LCS, 如果你知道其中有一个是单调的, 就能在linear时间中找到.
☆─────────────────────────────────────☆
rentny2007 (rent) 于 (Sun Oct 25 15:26:05 2009, 美 |
|
