当前位置：文江博客话题详情

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

发布于 2024-12-12 03:43:43 字数 138 浏览 0 评论 0原文

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

我的书没有涉及 LIS，所以我有点不知道如何开始。对于 DP 表，我对最长公共子序列做了类似的事情。任何有关如何开始此操作的帮助将不胜感激。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

左秋 2024-12-19 03:43:43

关于这个主题已经有很多答案，但这是我的演练，我将此网站视为未来后代答案的存储库，这只是为了在我自己完成它时提供额外的见解。

最长递增子序列（LIS）问题是找到给定序列的最长子序列的长度，使得该序列的所有元素
子序列按升序排序。例如，

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

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

现在迭代输入集中的每个整数 X 并执行以下操作

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

否则找到S中大于等于X的最小元素，将其改为X。因为S随时都已排序，所以可以找到该元素
在 log(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< /code>，然后追加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 之后的 code>2，
你如何处理这些。好吧，2,3,4 块实际上不会做任何事情，当您点击 5 时，您会替换 9 因为 5 和 9
实际上是不可微分的 9 结束了第一个 5 递增元素的块，您将 9 替换为 5 因为 5 较小，所以有
击中某物的潜力更大> 5 稍后。但你只替换最小的元素>本身。对于前。在最后一种情况下，
如果您的 6 没有替换 9 而是替换 1 并且 7 替换 2 > 和 8 替换 3，然后我们得到一个由 7 个元素组成的最终数组
9. 所以只要做几个这样的事情并找出模式，这个逻辑并不是最容易转化为纸质的。

Already plenty of answers on this topic but here's my walkthrough, I view this site as a repository of answers for future posterity and this is just to provide additional insight when I worked through it myself.

The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the
subsequence are sorted in increasing order. For example, length of LIS for

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

Let S[pos] be defined as the smallest integer that ends an increasing sequence of length pos.

Now iterate through every integer X of the input set and do the following:

If X > last element in S, then append X to the end of S. This essentialy means we have found a new largest LIS.

Otherwise find the smallest element in S, which is >= than X, and change it to X. Because S is sorted at any time, the element can be found
using binary search in log(N).

Total runtime - N integers and a binary search for each of them - N * log(N) = O(N log N)

Now let's do a real example:

Set of integers: 2 6 3 4 1 2 9 5 8

Steps:

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).

Let's take some other sequences to see that this will cover all possible caveats, each presents its own issue

say we have 1,2,3,4,9,2,3,4,5,6,7,8,10

basically it builds out 12349 first, then 2 will replace 3, 3 will replace 4, 4 will replace 9, then append 5,6,7,8,10
so will look like 1,2,2,3,4,6,7,8,10

take the other case we have 1,2,3,4,5,9,2,10
this will give us 1,2,2,4,5,9,10

or take the case we have 1,2,3,4,5,9,6,7,8,10
this will give us 1,2,3,4,5,7,8,10

so that kind of illuminates what goes on, in the first case the critical juncture being what happens when you hit the 2 after the 9,
how do you deal with these. well the block of 2,3,4 won't do anything really, when you hit 5 you replace the 9 because the 5 and 9
are virtually indifferentiable 9 ends the block of the first 5 increasing elements, you replace 9 with 5 because 5 is smaller so there
is greater potential to hit something > 5 later on. but you only replace the smallest element > itself. for ex. in the last case,
if your 6 doesn't replace 9 but instead replaces 1 and 7 replaces 2 and 8 replaces 3, then we get a final array of 7 elements instead
of 9. So just do a couple of these and figure out the pattern, this logic isn't the easiest to translate to paper.