最长递增子序列

✍ dations ◷ 2025-06-09 08:42:47 #组合数学,动态规划

在计算机科学中,最长递增子序列(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() 项中的恒定因子)而言,这是最佳选择。

相关

  • 中胶层中胶层是存在于腔肠动物体表的两层上皮细胞之间的一种透明、胶状物质。中胶层的主要构成物质是水。除此之外,还包括几种纤维状蛋白,例如胶原质和硫酸乙酰肝素蛋白聚糖。 中胶
  • 酞嗪酞嗪(英语:Phthalazine)是一种杂环化合物,化学式C8H6N2,由一个苯环与一个哒嗪环稠合而成。喹唑啉也可看做萘环的两个CH被N原子替换,这样的结构称为萘啶。酞嗪及其衍生物不存在于自
  • 太阳光发电太阳光伏系统,也称为光生伏特,简称光伏(Photovoltaics;字源“photo-”光,“voltaics”伏特),是指利用光伏半导体材料的光生伏打效应而将太阳能转化为直流电能的设施。光伏设施的核
  • 芽笼芽笼(Geylang)与芽笼士乃(Geylang Serai),是城市国家新加坡之一个社区,在新加坡金融区以东,位于新加坡河的东部。早于十九世纪初新加坡开埠初年,芽笼已出现于典籍内。1822年,当新加坡
  • 润饼薄饼卷,又称薄饼、润饼、嫩饼菜,台湾中南部地区亦称为春卷,是一种用薄饼卷食其他肉菜等的食品。状似春卷,但卷好熟食后直接食用,无须油炸。润饼作为闽南饮食文化的一部分,流行于福
  • 钱 前钱前(1962年3月-),安徽安庆人,中国水稻研究所副所长、研究员,水稻生物学国家重点实验室主任。2019年当选为中国科学院院士。1983年毕业于南开大学,获学士学位。1989年毕业于日本北
  • 天然宿主自然宿主(natural reservoir,亦作reservoir host),又名存储宿主、保虫宿主或储蓄宿主,是一个流行病学或感染性生态学(英语:disease ecology)的专有名词,指病原体天然栖息及繁殖,又或赖
  • 阿希尔·巴拉杰·迪里埃路易-阿希尔·巴拉杰·迪里埃,第一代巴拉杰·迪里埃伯爵(Louis-Achille Baraguey d'Hilliers, 1st Comte Baraguey d'Hilliers) (1795年9月6日-1878年6月6日) 法国元帅和政治家
  • 佩尔迪海滩 (阿拉巴马州)佩尔迪多海滩(英文:Perdido Beach),是美国阿拉巴马州下属的一座城市。面积约为1.24平方英里(约合 3.22平方公里)。根据2010年美国人口普查,该市有人口581人,人口密度为467.04/平方英
  • 燕垒生燕垒生(1970年10月-),也作燕垒,原名张健,中国网络作家、诗人。燕垒生毕业于中国计量学院,其后就职于余杭区国家税务局管理一科,1998年开始网络诗歌写作,2000年在榕树下举办的比赛中获