问题标签 [lis]

我有一组整数。我想使用动态编程找到该集合的最长递增子序列。

你得到一个数字序列，你需要从给定的输入中找到一个最长的递增子序列（不一定是连续的）。

我找到了这个链接（维基百科上最长的增加子序列），但需要更多解释。

如果有人可以帮助我理解 O(n log n) 的实现，那将非常有帮助。如果你能用一个例子来解释这个算法，那将非常感激。

我也看到了其他帖子，但我不明白的是：L = 0 for i = 1, 2, ... n: 二分查找最大正数 j ≤ L 使得 X[M[j]] < X [i] （如果不存在这样的值，则设置 j = 0）上面的语句，从哪里开始二分查找？如何初始化 M[]、X[]？

LIS：维基百科

有一件事我无法理解：

为什么 X[M[i]] 是非递减序列？

我试图理解在时间 O(n k log(n)) 中为我提供数组中长度为 K 的递增子序列数量的算法。我知道如何使用 O(k*n^2) 算法来解决同样的问题。我查了一下，发现这个解决方案使用 BIT (Fenwick Tree) 和 DP。我也找到了一些代码，但我一直无法理解。

以下是我访问过的一些有用的链接。

在 SO
Topcoder 论坛
随机网页中

如果有人能帮助我理解这个算法，我将不胜感激。

这是我为寻找最长递增子序列而设计的程序。我正确地获得了子序列的长度，但我没有正确地获得序列。我认为包含变量的最后一个 for 循环可能存在问题k，但我无法弄清楚。请帮我。

这是维基百科上给出的最长递增子序列的伪代码

我已经了解代码是如何工作的。我唯一不能理解的是这个语句的必要性（如果 j == L 或 X[i] < X[M[j+1]]:) 我已经尝试在许多示例上运行该算法，我可以做出什么是在所有情况下，要么 j == L 要么 X[i] < X[M[j+1]] ，所以 if 语句总是计算为 True。你能给我一个例子，if循环是假的，因此算法需要吗？

你会得到n一对数字。在每一对中，第一个数字总是小于第二个数字。当且仅当小于时，一对(c,d)可以跟随。可以以这种方式形成对链。找到形成的最长链对。(a,b)bc

我在接受亚马逊采访时得到了这个问题，但无法弄清楚答案，只是它与LIS 问题有关。

我有事困扰我。我正在尝试解决以这些信息为指导的建筑桥梁问题。

建造桥梁
考虑一张 2-D 地图，其中有一条水平河流穿过其中心。南岸有 n 个城市，x 坐标为 a(1) ... a(n)，北岸有 n 个城市，x 坐标为 b(1) ... b(n)。
您希望通过桥梁连接尽可能多的南北城市对，以使没有两座桥梁交叉。连接城市时，只能连接北岸i市和南岸i市。”

我对 Stack Overflow 进行了研究，发现了一些对我有很大帮助的主题，例如：
搭建桥梁问题 - 如何应用最长递增子序列？ 以及
如何使用动态规划确定最长的递增子序列？

但是当我想出 LIS 并尝试手动解决一个示例列表时。假设我有

排序后的南岸

LIS 长度假设为“5”，但实际上在第一个列表中，只有 3 个桥能够创建 (3,2,1)。那么我是否误解了LIS，或者有任何例外不适用于构建桥梁问题？

我发现The Hitchhiker's Guide to the Programming Contests中提到的算法（注意：此实现假定列表中没有重复项）：

这是一种在 O(NlogN) 中找到最长递增子序列的算法。如果我尝试使用很少的测试用例来处理它，它似乎可以工作。但我仍然无法弄清楚它的正确逻辑。此外，它对我来说看起来并不那么直观。

谁能帮我深入了解为什么这个算法可以正常工作？

来自 SPOJ，这是问题陈述。我从正常的 DP 解决方案开始，但这需要 n^2 时间，并且必然会超过时间限制。

我遇到了该问题的 nlogn 解决方案，这是解决方案。

如果我们只需要找到最长递增子序列的长度，或者如果您也必须找到其中一个序列，则该解决方案效果很好。但是如果你必须找到属于一个序列或另一个序列的所有元素，我做了一些存储和其他工作，我已经达到了这个解决方案。

现在这是 SPOJ 引擎所期望的，但是当我查看其他公认的解决方案时，我的程序需要 0.48 的时间，而其他程序需要低至 0.04 的时间。

我想知道，如果可能的话，有人可以告诉我如何改进我的解决方案吗？

我在我的解决方案中所做的是，在输出数组中，我不仅存储当前数字，而且存储整个列表，在父级中，我维护所有的父级，因为每个数字都成为输出的一部分大批。

最终的数组只不过是最终的整数数组，它存储布尔值，该数字是否属于 LIS。

谢谢

PS 它说指向 ideone.com 的链接必须附有代码，因此将代码本身粘贴到此处。