最长上升子序列(LIS)和最长公共子序列(LCS)

区别于字符串,序列并不一定是连续的。最长上升子序列(LIS)和最长公共子序列(LCS)算法是基础的序列算法。

最长公共子序列(LCS)

这是一个经典的dp问题,使用dp[i][j]表示表示序列X的i位和序列Y的j位之前的最长公共子序列的长度。那么如果X[i] == Y[j]dp[i][j] = dp[i+1][j+1] + 1;否则dp[i][j] = max{d[[i-1][j], dp[i][j-1], dp[i-1][j-1]}

例题 POJ 1458 Common Subsequence

第一次写成这样
应该是这样

最长上升子序列(LIS)

$O(n^2)$方法

运用动态规划的方法,记录$ l_i $为序列$a_{1..(i-1)}$中前$i - 1$个数中最长的上升序列长度。现在需求$l_i$,考虑将$a_i$插在以$i$前面的某个元素$a_j$的结尾的子序列的后面,那么就是要满足以下条件:

  1. $a_i > a_j$ ,这是显然和必须的,否则这个序列就不是上升子序列
  2. $l_j$最长

因此,对于$a_{i+1}$,需要找出最大的$l[m]$并且$a[m] < a[i]$。可以发现复杂度为$O(n^2)$。
容易发现,寻找最大的$l_j$可以使用二分法。因此可以得到下面的$O(NlogN)$方法。

区间段问题

为了更好地理解下面的$O(NlogN)$方法,可以考虑有若干个任务具有不同的起止时间,在同一时间只能做同一任务,并且该任务完成后才能开始新的任务。现在要求找出能够完成的最多任务数。
容易想到这是一个贪心问题。事实上每次选取结束时间最早的任务,这样保证了剩下的时间短尽可能地长,而一个较长的时间段肯定比它的较短的部分的可选工作数要多(至少不会变少)。

O(NlogN)方法

这个方法与区间段问题的思想类似,要使得上升子序列最长,就要使得序列上升尽可能慢,因此我们希望每次在序列最后加上的数尽可能小,当然由于数列的长度是有限的,所以不一定这样能得到足够长的LIS序列,所以我们在确定新得到的LIS数列足够长的时候再更新长度。
因此我们记录$dp[i]$为长度为$i$的LIS序列的末尾元素的值,使用动态规划依次计算$dp[1..n]$。我们使用$len$记录目前最长LIS的长度,显然$dp[i]$关于$i$是单调不减的。这是因为如果我们假设$dp[i] = 3$、$dp[i - 1] = 4$,那么$dp[i]$还多取一个数,所以也至少应该取到4。当使用$a[j]$更新$dp$时,我们顺着$dp[1]$开始找,一旦发现$dp[i-1] < a_j < dp[i]$,那么可以用$a[j]$更新$dp[i]$,同时如果当前的$i$(从1开始)大于记录的$len$时,用$i$更新$len$。
需要注意的是,虽然在原序列中$a[j]$出现在$dp[i]$对应的$a[j]’$之后,如果$a[j]$包含在序列中,那么比$a[j]$大的$a[j]’$显然不会包含在序列中,但是这不影响取得最大值,因为除非从$a[j]$开始的新序列能够去得更长的$len$,否则仍然取得的是当前的序列。
此外,在找到$j$之后不要更新后面的$dp[i + 1..n]$,因为每取一个$a$,向后面递推一次$dp$。
在寻找时,考虑到dp是一个不降序列,可以使用lower_bound函数(内部采用二分查找)。这个函数将会返回大于等于val的第一个值的指针,如果不存在就返回end指针,在使用时候注意区别upper_bound函数,upper_bound函数返回的是严格大于val的第一个值。注意指针的差值从0开始,但是序列长度从1开始,所以得到的差值转换成长度要加1。

例题 HDU 5532 Almost Sorted Array

此题题意要求找出一个序列是否可以去掉最多一个元素形成一个sorted array。因此可以正反(考虑到可能是不升序列也可能是不降序列)求一次LIS(不降子序列),那求出的最长上升子序列的长度至少要大于等于n-1那么就是满足题意的。当然这道题目也可以用O(n)实现。O(n)算法需要注意不能只判断连续情况。

最长公共上升子序列(LCIS)