区别于字符串，序列并不一定是连续的。最长上升子序列(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$的结尾的子序列的后面，那么就是要满足以下条件：
- $a_i > a_j$ ，这是显然和必须的，否则这个序列就不是上升子序列
- $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)算法需要注意不能只判断连续情况。
