最长递增子序列

✍ dations ◷ 2025-04-08 05:48:53 #组合数学,动态规划

在计算机科学中,最长递增子序列(longest increasing subsequence)问题是指,在一个给定的数值序列中,找到一个子序列,使得这个子序列元素的数值依次递增,并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、随机矩阵理论(英语:random matrix theory)、表示论相关的研究都会涉及最长递增子序列。解决最长递增子序列问题的算法最低要求O( log )的时间复杂度,这里表示输入序列的规模。

对于以下的原始序列

最长递增子序列为

值得注意的是原始序列的最长递增子序列并不一定唯一,对于该原始序列,实际上还有以下两个最长递增子序列

最长递增子序列问题与最长公共子序列问题密切相关,后者具有动态规划解决方案(时间复杂度为O):序列S的最长递增子序列是S和T的最长公共子序列,其中T是对S进行排序的结果。但对于特殊情况,输入是整数 1, 2, ..., , 的排列,解决方案可以进一步改进,从而使时间复杂度降为O( log ) 。

排列图(permutaion graph)中的最大团是由'定义该图的排列中最长的递减子序列'定义的, 求最长的递减子序列在计算复杂度上(通过对所有数取它的负数)等同于求最长的递增子序列。 因此,最长递增子序列算法可用于有效地解决排列图中的分团问题。

下面概述的算法使用数组和二分查找算法有效地解决了最长递增子序列问题。 它依次处理序列元素,保存当前找到的最长的递增子序列, 比如: ,X ]。在处理X之后,算法会将值存储在两个数组中:

另外,该算法还存储了一个变量L,该变量L表示到目前为止找到的最长的递增子序列的长度。 下面的算法使用基于零的编号,为了清楚起见,M用M 填充,而M 未使用,因此M 对应于长度j的子序列。 实际的实现可以跳过M 并相应地调整索引。

请注意,在算法的任何时候,序列

是递增的。 因为,如果长度的子序列以X ]结尾,则长度的子序列以较小的值结尾:即以X 结尾的子序列 ]。 因此,我们可以使用二分查找在时间内完成搜索。

伪代码如下:

P = array of length NM = array of length N + 1L = 0for i in range 0 to N-1:    // Binary search for the largest positive j ≤ L    // such that X] <= X    lo = 1    hi = L    while lo ≤ hi:        mid = ceil((lo+hi)/2)        if X] < X:            lo = mid+1        else:            hi = mid-1    // After searching, lo is 1 greater than the    // length of the longest prefix of X    newL = lo    // The predecessor of X is the last index of     // the subsequence of length newL-1    P = M    M = i        if newL > L:        // If we found a subsequence longer than any we've        // found yet, update L        L = newL// Reconstruct the longest increasing subsequenceS = array of length Lk = Mfor i in range L-1 to 0:    S = X    k = Preturn S

由于该算法对每个序列元素都执行二分查找,因此时间复杂度为O( log )。 弗雷德曼 Fredman (1975)讨论了该算法的一种变体,他将其归功于高德纳。 在他研究的变体中,该算法在进行二分查找之前,测试每个值X 是否可以在常数时间内扩展当前最长的递增序列。 通过这种修改,算法在最坏的情况下只会进行 log2 − log2log2 + O()个比较,对于比较算法(最高为O() 项中的恒定因子)而言,这是最佳选择。

相关

  • 转移酶转移酶是一种催化一个分子(称为供体)的官能团(如甲基或磷酸盐团)转移至另一个分子(称为受体)的酶。 举例来说,一种酶催化以下的化学反应就是转移酶:在这例子中的A就是供体,而B就是受
  • 新近纪新近纪(英语:Neogene,符号N),旧称晚第三纪,是地质年代中一个纪,开始于同位素年龄23.03±0.05百万年,距今2.6百万年结束,持续了21.4百万年。新近纪内,动、植物已接近现代。货币虫已完全
  • 柳成龙柳成龙(1542年11月7日(嘉靖二十一年十月初一)-1607年6月7日(万历三十五年五月十三日)),字而见,号西厓,安东丰山(今韩国庆尚北道安东市丰山邑)人,是朝鲜王朝时期的政治家。他是柳仲郢的次
  • 透析 (生物化学)在 生物化学中, 透析过程是利用不同分子扩散性质的差异而分离溶液中的分子 ,通常借由一层半渗透膜(如透析管)工具达成。透析是常见的实验室技术,与医学上人工透析(洗肾)使用同样的
  • 涮羊肉涮羊肉是一种流行于北京及其周边地区的传统火锅,因食材主要以羊肉为主,故而得名。实际上,传统涮羊肉也讲究白菜、豆腐、粉丝等几类羊肉以外的食材。现代也开始将牛肉片作为涮羊
  • 保守序列保守序列(英语:conserved sequences)在生物学中是指在核酸序列(如RNA及DNA序列)、蛋白质序列、蛋白质结构或多聚糖序列内相似或相同的序列,这种情况可以发生在各物种间(种间同源序
  • 卡琳娜·卡浦尔卡琳娜·卡浦尔(英语:Kareena Kapoor,印地语:करीना कपूर,1980年9月21日-)是活跃于二十一世纪前期的印度著名宝莱坞女演员。她出生于印度知名演艺世家卡浦尔家族,姐姐是女演
  • 战略大作战《战略大作战》(英语:Kelly's Heroes)是1970年由米高梅公司制作,克林·伊斯威特、特利·萨瓦拉斯主演的战争喜剧片。二战期间,一支美国军团受困于进军法国南部。情况紧急之际,一名
  • 弗里德里希·冯·弗洛托弗里德里希·阿道夫·费迪南德·冯·弗洛托(德语:Friedrich Adolf Ferdinand von Flotow,1812年4月27日-1883年1月24日),德国作曲家。1827年赴巴黎师从雷哈,期间结识了梅耶贝尔,罗西
  • 梦幻岛梦幻岛(英语:Neverland)出自于苏格兰小说家及剧作家詹姆士·马修·巴里笔下的《彼得潘》,是处于遥远地方的虚构地点,主角彼得潘(Peter Pan)、仙子小叮当(英语:Tinker Bell)(Tinker Bell