LIS

最长上升子序列$（Longest \; Increasing \: Subsequence）$，简称$LIS$，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。假设我们有一个序列 $b_i$，当$b_1 < b_2 < … < b_S$的时候，我们称这个序列是上升的。对于给定的一个序列$(a_1, a_2, …, a_N)$，我们也可以从中得到一些上升的子序列$(a_{i1}, a_{i2}, …, a_{iK})$，这里$1 \leq i_1 < i_2 < … < i_K \leq N$，但必须按照从前到后的顺序。比如，对于序列$(1, 7, 3, 5, 9, 4, 8)$，我们就会得到一些上升的子序列，如$(1, 7, 9), (3, 4, 8), (1, 3, 5, 8)$等等，而这些子序列中最长的（如子序列$(1, 3, 5, 8)$），它的长度为$4$，因此该序列的最长上升子序列长度为$4$。

看了上面你一定很懵吧...下面细讲

首先需要知道，子串和子序列的概念，我们以字符子串和字符子序列为例，更为形象，也能顺带着理解字符的子串和子序列：

（1）字符子串指的是字符串中连续的$n$个字符，如 $abcdefg$中，$ab$，$cde$，$fg$等都属于它的字串。

（2）字符子序列指的是字符串中不一定连续但先后顺序一致的$n$个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。如$abcdefg$中，$acdg$，$bdf$属于它的子序列，而$bac$，$dbfg$则不是，因为它们与字符串的字符顺序不一致。

知道了这个，数值的子序列就很好明白了，即用数组成的子序列。这样的话，最长上升子序列也很容易明白了，归根结底还是子序列，然后子序列中，按照上升顺序排列的最长的就是我们最长上升子序列了，这样听来是不是就很容易明白啦～

还有一个非常重要的问题：请大家用集合的观点来理解这些概念，子序列、公共子序列以及最长公共子序列都不唯一，但很显然，对于固定的数组，虽然LIS序列不一定唯一，但LIS的长度是唯一的。再拿我们刚刚举的栗子来讲，给出序列 ($1, 7, 3, 5, 9, 4, 8$)，易得最长上升子序列长度为4,这是确定的，但序列可以为 $(1, 3, 5, 8)$, 也可以为 ( $1, 3, 5, 9)$。

LCS

最长公共子序列，英文缩写为$LCS（Longest Common Subsequence）$。其定义是，一个序列 $S$ ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 $S$ 称为已知序列的最长公共子序列。

如果觉得抽象不好理解，那么咱们还是采用学习LIS的时候的方式。首先，让我们先来看一下 子串 、子序列还有公共子序列的概念(在上篇LIS中也曾涉及过) ，我们以字符子串和字符子序列为例，更为形象，也能顺带着理解字符的子串和子序列：

（1）字符子串： 指的是字符串中连续的$n$个字符，如$abcdefg$中，$ab$，$cde$，$fg$等都属于它的字串。

（2）字符子序列： 指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。如$abcdefg$中，$acdg$，$bdf$属于它的子序列，而$bac$，$dbfg$则不是，因为它们与字符串的字符顺序不一致。

(3) 公共子序列： 如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。如对序列 $1,3,5,4,2,6,8,7$和序列 $1,4,8,6,7,5$ 来说，序列$1,8,7$是它们的一个公共子序列。

那么现在，我们再通俗的总结一下 最长公共子序列（LCS）： 就是$A$和$B$的 公共子序列中长度最长的 （包含元素最多的）

仍然用序列$1,3,5,4,2,6,8,7$和序列$1,4,8,6,7,5$为例，它们的最长公共子序列有$1,4,8,7$和$1,4,6,7$两种，但最长公共子序列的长度是$4$。由此可见， 最长公共子序列（LCS）也不一定唯一 。

请大家用集合的观点来理解这些概念，子序列、公共子序列以及最长公共子序列都不唯一，所以我们通常特判取一个最长公共子序列，但很显然， 对于固定的两个数组，虽然最LCS不一定唯一，但LCS的长度是一定的 。查找最长公共子序列与查找最长公共子串的问题不同的地方在于：子序列不需要在原序列中占用连续的位置。最长公共子串（要求连续）和最长公共子序列是不同的。