求解给定序列的最长递增子序列

更新：无代码，多图预警！

声明：非科班算法渣写的文章，谨慎的看，文章中有任何错误请不吝指出，更希望大佬们能提供更多信息交流，让我进步。

最长递增子序列在Virtual DOM算法中的意义

如果了解过 ivi/inferno 的同学应该知道，在 ivi/inferno 中 Virtual DOM 的核心 Diff 算法中应用到了求解给定序列的最长递增子序列的算法，用的算法来自：en.wikipedia.org/wiki/Longes… 。当然了，这篇文章不是用来讲解这个链接中所描述的算法的，而是单纯的想要解决：找到给定序列的*所有*最长递增子序列。

这里不会讲解 ivi/inferno 中核心 Diff 的实现，但是有些信息需要做出陈述：新旧 children 中的节点有各自的顺序，如下图所示：

ivi/inferno 会构建一个 source 数组，数组中的值存储的就是新 children 中的节点在旧 children 中的位置，如上图所示 source 数组为：[ 2, 3, 1, -1 ]。接着如果节点需要移动的话，则会把 source 数组中的数值作为一个序列，并求解它的最长递增子序列。对于序列 [ 2, 3, 1, -1 ] 来说，它的最长递增子序列就是 [ 2, 3 ]，但实际上我们需要的并不是子序列本身，而是子序列中的元素在 source 数组中的位置，也就是 [ 0, 1 ]。那么 [ 0, 1 ] 的作用是什么呢？它意味着在新 children 中位于第 0 和 第 1 个位置的节点是不需要被移动的，换句话说在上图中只有 li-b 节点是需要被移动的，这种方式能够保证移动在 DOM 操作中总是拥有最少的移动次数，但是如何证明它是最少的目前我也不知道，因为我尝试了很多个案例，发现 snabbdom 的移动次数并不会比 ivi/inferno 多。所以也希望了解的大佬们指点一下（我单纯的指移动 DOM 的次数，而非总体的性能）。

求解给定序列的最长递增子序列

什么是最长递增子序列这里引用一段描述：

不废话了，设给定的序列如下：

[ 0, 8, 4, 12, 2, 10 ]

实际上，这是一个可以利用动态规划思想求解的问题。动态规划的思想是将一个大的问题分解成多个小的子问题，并尝试得到这些子问题的最优解，子问题的最优解有可能会在更大的问题中被利用，这样通过小问题的最优解最终求得大问题的最优解。那么对于一个序列而言，它的子问题是什么呢？很简单，序列是有长度的，所以我们可以通过序列的长度来划分子问题，如上序列所示，它有 6 个元素，即该序列的长度为 6，所以我们可不可以将这个序列拆解为长度更短的序列呢？并优先求解这些长度更短的序列的最长递增子序列，进而求得原序列的最长递增子序列？答案是肯定的，假设我们取出原序列的最后一个数字单独作为一个序列，那么该序列就只有一个元素：[ 10 ]，很显然这个只有一个元素的序列的长度为 1，已经不能更短了。那么序列 [ 10 ] 的最长递增子序列是什么呢？因为只有一个元素，所以毫无递增可言，但我们需要一个约定：*当一个序列只有一个元素时，我们认为其递增子序列就是其本身，所以序列 [ 10 ] 的最长递增子序列也是 [ 10 ]，其长度也是 1。

接着我们将子问题进行扩大，现在我们取出原序列中的最后两个数字作为一个序列，即 [ 2, 10 ]。对于这个序列而言，我们可以把它看作是由序列 [ 2 ] 和序列 [ 10 ] 这两个序列所组成。并且我们观察这两个序列中的数字，发现满足条件 2 < 10，这满足了递增的要求，所以我们是否可以认为序列 [ 2, 10 ] 的最长递增子序列 等于 序列 [ 2 ] 和序列 [ 10 ] 这两个序列的递增子序列“之和”？答案是肯定的，而且庆幸的是，我们在上一步中已经求得了序列 [ 10 ] 的最长递增子序列的长度是 1，同时序列 [ 2 ] 也是一个只有一个元素的序列，所以它的最长递增子序列也是它本身，长度也是 1，最后我们将两者做和，可知序列 [ 2, 10 ] 的最长递增子序列的长度应该是 1 + 1 = 2。实际上，我们一眼就能够看得出来序列 [ 2, 10 ] 的最长递增子序列也是 [ 2, 10 ]，其长度当然为 2 啦。

为了不过与抽象，我们可以画出如下图所示的格子：

我们为原序列中的每个数字分配一个格子，并为这些格子填充 1 作为初始值：

根据前面的分析，我们分别求得子问题的序列 [ 10 ] 和 [ 2, 10 ] 的最长递增子序列的长度分别为 1 和 2，所以我们修改对应的格子中的值，如下：

如上图所示，原序列中数字 10 对应的格子的值依然是 1，因为序列 [ 10 ] 的最长递增子序列的长度是 1。而原序列中数字 2 对应的格子的值为 2，这是因为序列 [ 2, 10 ] 的最长递增子序列的长度是 2。所以你应该发现了格子中的值所代表的就是以该格子所对应的数字为开头的递增子序列的最大长度。

接下来我们继续扩大子问题，我们取出原序列中的最后三个数字作为子问题的序列：[ 12, 2, 10 ]。同样的，对于这个序列而言，我们可以把它看作是由序列 [ 12 ] 和序列 [ 2, 10 ] 这两个序列所组成的。但是我们发现条件 12 < 2 并不成立，这说明什么呢？实际上这说明：以数字 12 开头的递增子序列的最大长度就 等于 以数字 2 开头的递增子序列的最大长度。这时我们不需要修改原序列中数字 12 所对应的格子的值，如下图所示该格子的值仍然是 1：

但是这就结束了吗？还不行，大家思考一下，刚刚我们的判断条件是 12 < 2，这当然是不成立的，但大家不要忘了，序列 [ 12, 2, 10 ] 中数字 2 的后面还有一个数字 10，我们是否要继续判断条件 12 < 10 是否成立呢？当然有必要，道理很简单，假设我们的序列是 [ 12, 2, 15 ] 的话，你会发现，如果仅仅判断条件 12 < 2 是不够的，虽然数字 12 不能和数字 2 构成递增的关系，但是数字 12 却可以和数字 15 构成递增的关系，因此我们得出当填充一个格子的值时，我们应该拿当前格子对应的数字逐个与其后面的所有格子对应的数字进行比较，而不能仅仅与紧随其后的数字作比较。按照这个思路，我们继续判断条件 12 < 10 是否成立，很显然是不成立的，所以原序列中数字 12 对应的格子的值仍然不需要改动，依然是 1。

接着我们进一步扩大子问题，现在我们抽取原序列中最后的四个数字作为子问题的序列：[ 4, 12, 2, 10 ]。还是同样的思路，我们可以把这个序列看作是由序列 [ 4 ] 和序列 [ 12, 2, 10 ] 所组成的，又因为条件 4 < 12 成立，因此我们可以认为这个序列的最长递增子序列的长度等于序列 [ 4 ] 的最长递增子序列的长度与以数字 12 开头的递增子序列的最大长度之和，序列 [ 4 ] 的最长递增子序列的长度很显然是 1，而以数字 12 开头的递增子序列的最大长度实际上就是数字 12 对应的格子中的数值，我们在上一步已经求得这个值是 1，因此我们修改数字 4 对应的格子的值为 1 + 1 = 2：

当然了，这同样还没有结束，我们还要判断条件 4 < 2 和 4 < 10 是否成立，原因我们在前面已经分析过了。条件 4 < 2 不成立，所以什么都不做，但条件 4 < 10 成立，我们找到数字 10 对应的格子中的值： 1，将这个值加 1 之后然的值为 2，这与现在数字 4 对应的格子中的值相等，所以也不需要改动。

到现在为止，不知道大家发现什么规律没有？如何计算一个格子中的值呢？实际很简单，规则是：

一、拿要填充的格子对应的数字 a 与其后面的所有格子对应的数字 b 进行比较，如果条件 a < b 成立，则用数字 b 对应格子中的值加 1，并将结果填充到数字 a 对应的格子中。 二、只有当计算出来的值大于数字 a 所对应的格子中的值时，才需要更新该格子中的数值。

有了这两条规则，我们就很容易填充剩余格子的值了，接下来我们来填充原序列中数字 8 所对应的格子的值。按照上面的分析，我们需要判断四个条件：

1、8 < 4 2、8 < 12 3、8 < 2 4、8 < 10

• 很显然条件 8 < 4 不成立，什么都不做；
• 条件 8 < 12 成立，拿出数字 12 对应格子中的值：1，为这个值再加 1 得出的值为 2，大于数字 8 对应格子的当前值，所以更新该格子的值为 2；
• 条件 8 < 2 也不成立，什么都不做；
• 条件 8 < 10 成立，拿出数字 10 对应格子中的值 1，为这个值再加 1 得出的值为 2，不大于数字 8 所对应格子中的值，所以什么都不需要做；

最终我们为数字 8 所对应的格子填充的值是 2：

现在，就剩下原序列中数字 0 对应的格子的值还没有被更新了，按照之前的思路，我们需要判断的条件如下：

1、0 < 8 2、0 < 4 3、0 < 12 4、0 < 2 5、0 < 10

条件 0 < 8 成立，拿出数字 8 对应格子中的值：2，为这个值再加 1 得出的值为 3，大于数字 0 对应格子的当前值，所以更新该格子的值为 3。重复执行上面介绍的步骤，最终原序列中数字 0 对应格子的值就是 3：

如上图所示，现在所有格子的值都已经更新完毕，接下来我们要做的就是根据这些值，找到整个序列的最长递增子序列。那么应该如何寻找呢？很简单，实际上这些格子中的最大值就代表了整个序列的递增子序列的最大长度，上图中数字 0 对应格子的值为 3，是最大值，因此原序列的最长递增子序列一定是以数字 0 开头的：

接着你需要在该值为 3 的格子后面的所有格子中寻找数值等于 2 的格子，你发现，有三个格子满足条件，分别是原序列中数字 8、4、2 所对应的格子。假设你选取的是数字 4：

同样的，你需要继续在数字 4 对应的格子后面的所有格子中寻找到数值为 1 的格子，你发现有两个格子是满足条件的，分别是原序列中数字 12 和数字 10 所对应的格子，我们再次随机选取一个值，假设我们选择的是数字 10：

由于格子中的最小值就是数字 1，因此我们不需要继续寻找了。观察上图可以发现，我们选取出来的三个数字其实就是原序列的最长递增子序列：[ 0, 4, 10 ]。当然，你可能已经发现了，答案并非只有一个，例如：

关键在于，有三个格子的数值是 2，因此你可以有三种选择：

• [ 0, 8 ]
• [ 0, 4 ]
• [ 0, 2 ]

当你选择的是 [ 0, 8 ] 时，又因为数字 8 对应的格子后面的格子中，有两个数值为 1 的格子可供选择，所以你还有两种选择：

• [ 0, 8, 12 ]
• [ 0, 8, 10 ]

同样的，如果你选择的是 [ 0, 4 ]，也有两个选择：

• [ 0, 4, 12 ]
• [ 0, 4, 10 ]

但当你选择 [ 0, 2 ] 时，你就只有一个选择：

- [ 0, 2, 10 ]

这是因为数字 2 所对应的格子后面，只有一个格子的数值是 1，即数字 10 所对应的那个格子，因此你只有一种选择。换句话说当你选择 [ 0, 2 ] 时，即使数字 12 对应的格子的值也是 1，你也不能选择它，因为数字 12 对应的格子在数字 2 对应的格子的前面。

以上，就是我们求得给定序列的所有最长递增子序列的算法。

代码可以在这里看这里：

lis - CodeSandboxcodesandbox.io

这是利用上面的思路，计算一个最长递增子序列的实现。要求解全部的话也可以，我先把文章发了，后面会更新。