最长递增子序列

✍ dations ◷ 2025-09-19 06:27:39 #组合数学,动态规划

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

相关

  • 半衰期半衰期(英语:Half-life)是指某种特定物质的浓度经过某种反应降低到剩下初始时一半所消耗的时间,半衰期是研究反应动力学的一个容易测定的重要参数,数学上可以证明,只有一级反应的
  • 樟山寺坐标:24°58′23″N 121°34′46″E / 24.9730897°N 121.57938°E / 24.9730897; 121.57938樟山寺位于台湾台北市老泉街,为主祀十八手观音之佛教庙宇,俗称十八只手。该建物兴
  • 外寄生物感染外寄生物感染是指主要由外寄生物引起的寄生虫病。外寄生物即暂时或永久寄生于宿主体表的寄生物。例如:治疗外寄生物感染常使用杀外寄生虫药(英语:ectoparasiticide),以杀死外寄生
  • 氖的同位素氖(原子量:20.1797(6))共有19个同位素,其中有3个是稳定的。备注:画上#号的数据代表没有经过实验的证明,只是理论推测而已,而用括号括起来的代表数据不确定性。
  • 橡子槲果(英语:acorn),又称橡子,广义为山毛榉科栎属的橡、栎、槲等果实(而不是种子)的总称,狭义指栎树的果实,富含淀粉。山毛榉科植物是亚热带和温带森林的主要构成树种。其中橡树是亚热
  • 蓝染惣右介蓝染惣右介(日语:藍染 惣右介/あいぜん そうすけ )是日本漫画《BLEACH》中的登场人物。原为尸魂界担任护廷十三队五番队队长的死神,多年前篡位成为虚圈统治者,后来夺得崩玉时叛离
  • 地球战场《地球战场》(英语:)是美国科幻作家兼山达基教(科学教)创办人L·罗恩·贺伯特出版于1982年的一部科幻小说。贺柏特本人亦曾为亲自这部小说创作了一张名为“”的专辑,这张专辑在198
  • 钟廷生钟廷生(?-1856年),太平天国官员。清代广西省人。钟廷生早年参加金田起义。太平天国丙辰六年(1856年)钟廷生镇守武昌。钟廷生官至秋官副丞相。天京事变后,十一月,太平军从武昌撤退,钟廷
  • 大竹佑季大竹佑季(1987年5月21日-),日本宫城县山元町出身的女性歌手。之前是隶属于堀制作(东芝EMI)。曾就读宫城县第三女子高等学校、日出高等学校。2003年时,得过第28届“Horipro Talent S
  • 孔令灿孔令灿(1888年-?年),字瀞庵、印秋。山东省曲阜县人,孔府嫡系一贯堂支(高祖孔宪增是衍圣公孔昭焕次子),衍圣公孔德成年幼时,曾主持孔府府务。民国37年(1948年)在山东省第六选区当选第一届