查找最长递增子序列(LIS)

Question

给定A= {1,4,2,9,7,5,8,2}，找到LIS。显示填充的动态规划表以及如何找到解决方案。

我的书没有涵盖LIS，所以我对如何开始有点迷茫。对于DP表，我用最长的公共子序列做了类似的事情。任何关于如何开始这项工作的帮助都将不胜感激。

Answer 1

关于这个主题的答案已经很多了，但这里是我的演练，我将这个网站视为未来后代的答案存储库，这只是为了在我自己工作时提供额外的洞察力。

最长递增子序列(LIS)问题是寻找给定序列的最长子序列的长度，使得该子序列中的所有元素都按递增顺序排序。例如，LIS的长度为

{ 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}.

假设S[pos]被定义为结束长度pos递增序列的最小整数。

现在遍历输入集的每个整数X，并执行以下操作：

如果X> S中的最后一个元素，则将X附加到S的末尾。这本质上意味着我们找到了一个新的最大的LIS。

否则，找到S中最小的元素，它比X更小，并将其更改为X。因为S在任何时候都是排序的，所以可以使用二进制搜索在>= (N)中找到该元素。

总运行时-N个整数，并对每个整数进行二进制搜索-N* log(N) = O(N log N)

现在让我们来做一个真实的例子：

整数集:2 6 3 4 1 2 9 5 8

步骤：

0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - 6 > 2 so append that to S
3. S = {2, 3} - 6 is the smallest element > 3 so replace 6 with 3
4. S = {2, 3, 4} - 4 > 3 so append that to s
5. S = {1, 3, 4} - 2 is the smallest element > 1 so replace 2 with 1
6. S = {1, 2, 4} - 3 is the smallest element > 2 so replace 3 with 2
7. S = {1, 2, 4, 9} - 9 > 4 so append that to S
8. S = {1, 2, 4, 5} - 9 is the smallest element > 5 replace 9 with 5
9. S = {1, 2, 4, 5, 8} - 8 > 5 so append that to S
So the length of the LIS is 5 (the size of S).

让我们看一下其他一些序列，看看这将涵盖所有可能的警告，每个警告都有自己的问题

假设我们有1,2,3,4,9,2,3,4,5,6,7,8,10

基本上，它首先构建12349，然后2将替换3，3将替换4，4将替换9，然后添加5,6,7,8,10以使其看起来像1,2,2,3,4,6,7,8,10

以另一种情况为例，我们有1,2,3,4,5,9,2,10，这将给我们1,2,2,4,5,9,10

或者以我们有1,2,3,4,5,9,6,7,8,10的情况为例，这将给我们1,2,3,4,5,7,8,10

所以这就说明了发生了什么，在第一种情况下，关键时刻是当你在9之后点击2时发生了什么，你如何处理这些问题。2,3,4的代码块实际上不会做任何事情，当你点击5时，你替换了9，因为5和9实际上是不可微的，结束了第一个5递增元素的代码块，你用5替换9，因为<代码>D28更小，所以以后有更大的可能命中某些东西><代码>D29。但是您只替换了最小的元素>本身。对于ex。在最后一种情况下，如果您的6没有替换9，而是替换了1，7替换了2，8替换了3，那么我们最终得到了一个由7个元素组成的数组，而不是9个元素。所以只要做几个元素并弄清楚模式，这个逻辑就不容易转换到纸上了。

Answer 2

LIS和LCS之间有很强的联系。

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

我认为这篇文章很好地解释了这一点。基本上，您可以将一个问题简化为另一个问题(这是涉及动态编程的许多情况下的情况)。