取自http://chieh-min.blogspot.com/2009/01/lcs-lis.html
把他轉成LIS 是因為要追求O(nlogn)的速度
作法：
設有序列A，B。
記序列A中各個元素在B 中的位子(降序排列)
然後按在A中的位置依序列出
出按後求A的最長遞增子序列
例如：有A={a,b,a,c,x}，B={b,a,a,b,c,a}
則有 a = {6,3,2} , b = {4,1} , c = {5} , x = / ;（注意降序排列）
然後按A中的次序排出
{ a(6,3,2) , b(4,1) , a(6,3,2) , c(5) , x( ) } = { 6,3,2,4,1,6,3,2,5 }；
對此序列求最長遞增子序列即可~~
把他轉成LIS 是因為要追求O(nlogn)的速度
作法：
設有序列A，B。
記序列A中各個元素在B 中的位子(降序排列)
然後按在A中的位置依序列出
出按後求A的最長遞增子序列
例如：有A={a,b,a,c,x}，B={b,a,a,b,c,a}
則有 a = {6,3,2} , b = {4,1} , c = {5} , x = / ;（注意降序排列）
然後按A中的次序排出
{ a(6,3,2) , b(4,1) , a(6,3,2) , c(5) , x( ) } = { 6,3,2,4,1,6,3,2,5 }；
對此序列求最長遞增子序列即可~~
全站熱搜
留言列表
資訊工程 (4)
