问题标签 [lis]

我有一个习惯AbstractTableModel

该模型将数据存储在HashMap. 所以对于我的方法getValueAt(int rowIndex, int columnIndex)

我愿意

但是，我的数据有超过 2000 个条目，因此每当我必须为我的表获取数据时，每次都这样做会造成巨大的性能损失。

那么您可以推荐什么解决方案？

我应该尝试使用List来存储我的所有数据而不是HashMap？
使用表模型时存储数据的公认标准是什么？

感谢任何人的建议，我为这可能是一个愚蠢的问题表示歉意，但在涉及表格以及如何在表格中存储数据时，我并不是很好。

我有以下算法，效果很好

我尝试在这里为自己解释它http://nemo.la/?p=943并在这里解释它http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/以及在stackoverflow上

我想修改它以产生最长的非单调递增子序列

对于序列 30 20 20 10 10 10 10

答案应该是 4：“10 10 10 10”

但是带有 nlgn 版本的算法它不起作用。初始化 s 以包含第一个元素“30”并从第二个元素 = 20 开始。这是发生的情况：

1. 第一步：30不大于等于20，我们找到大于20的最小元素，新的s变成“20”

2. 第二步：20大于等于20。我们扩展序列，s现在包含“20 20”

3. 第三步：10不大于或等于20。我们找到大于10的最小元素，即“20”。新的s变成“10 20”

之后 s 将永远不会增长，算法将返回 2 而不是 4

我试图使用递归找到所有可能的最长递增子序列。当我尝试输入数组{10,22,9,33,21,50,41,40,60,55}时，它起作用了，输出为：

但是当我尝试输入数组时{2,-3,4,90,-2,-1,-10,-9,-8}，我得到了一个输出：

在这种情况下，我没有得到2 4 90. 我应该在我的代码中进行哪些更改以使其适合这种情况？

我现在正在尝试一段时间来提出一个想法，以最有效的方式计算给定整数数组中有多少个最长递增子序列。我不需要找到所有的子序列，只要它们有多少......我正在使用 Java。有任何想法吗？

我有长度为 n 的点列表（在下面的示例 n = 6 中），之后我根据这些默认点做了一些其他点，例如点 7 是由“与”点 5 和点 4 等等现在我的问题是基于我拥有的数据结构，我怎样才能检索公式链？例如对于第 10 点（递归或非递归），我怎么能说这一点来自哪里？

如果我想知道第 10 点是如何产生的，它必须返回如下内容：

我正在练习算法，我的任务之一是计算给定0 < n <= 10^6数字的所有最长递增子序列的数量。解决方案O(n^2)不是一个选项。

我已经实现了查找 LIS 及其长度（LIS 算法），但该算法将数字切换到尽可能低的值。因此，不可能确定具有先前数字（较大的数字）的子序列是否能够达到最长的长度，否则我猜我可以只计算那些开关。

关于O(nlogn)的任何想法？我知道应该使用动态编程来解决它。

我实现了一个解决方案，它运行良好，但它需要两个嵌套循环(i in 1..n) x (j in 1..i-1)。
所以我认为它是O(n^2)，但它太慢了。

我什至尝试将这些数字从数组移动到二叉树（因为在每次i迭代中，我都会查找所有较小的数字然后number[i] - 遍历元素i-1..1），但它甚至更慢。

示例测试：

编辑
最后，我发现这种“蛮力”方法是不对的。
所以我写了另外两种方法来解决LIS问题。

• 在原始数组和排序后的数组上使用 LCS。时间复杂度 = (n^2)。
• 使用 DP + 二分查找。时间复杂度 = O(nlgn)。

[代码在最后。]

【DP+二分查找法】

我最近在 hyper-v 上创建了一个全新的第 2 代虚拟机，并安装了最近发布的 ubuntu 14.04 版本。

即使在 apt-get update 之后，在启动时，我的 Windows server 2012 R2 Hyper-V 服务器也会在 hyper-v 事件日志中抱怨低级驱动程序

合成显示驱动程序：“Dev Ubuntu 14.04 Gen2”中的设备“Microsoft Synthetic Display Controller”已加载，但与服务器的版本不同。服务器版本 3.3 客户端版本 3.2（虚拟机 ID 9FC171E7-B2C6-4BD2-9FF0-253209B2A69D）。该设备可以工作，但这是不受支持的配置。这意味着在解决此问题之前不会提供技术支持。要解决此问题，请升级集成服务。要升级，请连接到虚拟机并从“操作”菜单中选择“插入集成服务安装磁盘”。（当然这似乎不起作用）

和

数据交换集成服务：Hyper-V 数据交换连接到虚拟机“Dev Ubuntu 14.04 Gen2”，但版本与 Hyper-V 预期的版本不匹配（虚拟机 ID 9FC171E7-B2C6-4BD2-9FF0-253209B2A69D）。框架版本：协商（3.0）-预期（3.0）；消息版本：协商 (4.0) - 预期 (5.0)。这是不受支持的配置。这意味着在解决此问题之前不会提供技术支持。要解决此问题，请升级集成服务。要升级，请连接到虚拟机并从“操作”菜单中选择“插入集成服务安装磁盘”（类似地，这似乎不起作用）。

此外，hyper-v 抱怨 Windows 2012 R2 hyper-V 管理器的“摘要”选项卡中的“集成服务：需要更新”。

我（显然是错误的）认为 Linux 集成服务已集成到内核中，因此 Trusty 将与 2012 R2 hyper-v 服务兼容。

谁能解释在哪里/如何获得 14.04 的更新集成服务包以及正确的安装过程，以便使用 hyper-v 2012 r2 完全支持我的 ubuntu 虚拟机？

非常感谢您的帮助，道格·科尔曼

我们可以在迭代数组时使用堆栈来记录不断增加的子序列。运行时间是线性的，因为每个元素进入和离开堆栈一次。

如果我们想输出实际的序列而不是它的长度，我们可以记录起始索引，然后找到它后面的所有元素的值更大。

这种线性时间算法有效吗？

我试图找到一个数组的所有最长递增子序列。我可以按照Wikipedia 上O(n log n)的建议使用二进制搜索找到一个这样的 LIS 。

有人可以帮助我，我如何扩展它来查找所有此类 LIS。我找不到比O(n²). 任何优化建议都会非常有帮助。