问题标签 [lis]

这是最长递增子序列问题的变体。假设您不想找到一个序列或计算有多少个序列，而是想识别可能是某个最长递增序列的一部分的项目。

例如，在列表中，1,2,4,3,0,5除零之外的所有项目都可以是最长递增子序列的一部分。

找到这些项目的策略是什么？它的效率如何？

我试图在http://www.spoj.com/problems/MCARDS/上解决关于 spoj 的 MCARDS 问题

我知道它涉及最长增加子序列逻辑，但经过多次尝试我没有找到这个问题的解决方案，所以我搜索解决方案，我找到以下解决方案：

上述解决方案中排列背后的逻辑是什么？

提前致谢

我正在尝试编写一个应该在 C++ 程序中使用 C 库（LIS 库）的程序。结构对象的创建/初始化似乎存在问题。

当我在 wikipediapage 上运行示例程序时：http ://en.wikipedia.org/wiki/Lis_%28linear_algebra_library%29它运行起来就像一个魅力，但当然它被编译为 C 程序。

在我的 C++ 代码中，我这样做如下：

当我运行此代码时，它在 lis_matrix_create 行给我一个访问冲突。似乎 A 有一个内存地址，它的数据成员（LIS_MATRIX 在 Lis.h 中定义为一个结构）尚未初始化，因此它们的地址为 NULL。

您能否告诉我如何创建 LIS_MATRIX，以便我可以像在维基百科页面上的示例代码中那样使用它？

先感谢您！

回复 Adam 和 Ross Ridge：我在 Windows 7 64 位上使用 Visual Studio 2013。Lis 库的手册说它兼容 Visual Studio 2008、2010 和 2012 编译器，也兼容 gcc 3.4 和 4.4 以及一些 IBM、Intel 和 PGI C++ 编译器，我希望 Visual Studio 2013 不会有问题。

此外，在这段代码中，如果我取出“extern C”块，并包含“stdio.h”而不是 iostream，它运行没有问题（所以我猜这意味着使用了 C 编译器？）。在我还包括 iostream 的那一刻，访问冲突就开始了。

当我在 android 列表上用后退键隐藏键盘时，它可以正常工作并且我添加了新项目。我想刷新列表而不使用返回键隐藏键盘。我的代码是：

我最近正在研究以下问题。 http://www.codechef.com/problems/D2

主厨正在为 DirectiPlex 就职派对策划自助餐，并邀请了所有人。在他们进来的路上，每位客人都会拿起一张纸，里面有一个随机数字（这个数字可以重复）。客人们随后与他们的朋友坐在圆桌旁。厨师现在决定他想玩一个游戏。他让你从你的桌子上随机挑选一个人，让他们大声读出他们的号码。然后，围绕桌子顺时针移动，每个人都会读出他们的号码。目标是找到形成递增子序列的那组数字。所有拥有这些号码的人都将有资格参加幸运抽奖！一位软件开发人员对这一前景感到非常兴奋，并希望最大限度地增加有资格参加幸运抽奖的人数。所以，他决定编写一个程序来决定谁应该先读取他们的号码，以最大限度地增加有资格参加幸运抽奖的人数。你能打败他吗？

输入

第一行包含t测试用例的数量（大约 15 个）。然后是t测试用例。每个测试用例由两行组成：

1. 第一行包含一个数字N，即被邀请参加聚会的客人人数。
2. 第二行包含以空格分隔的N数字a1, a2, ..., an，即按顺时针顺序写在纸上的数字。

输出

对于每个测试用例，打印一个包含单个数字的行，该数字是有资格参加抽奖的客人的最大数量。

约束

1 ≤ N ≤ 10000 您可以假设纸上的每个数字编号；ai是随机生成的，即可以以相等的概率出现区间 中的任何数字[0,U]，其中U是某个上界 ( 1 ≤ U ≤ 106)。

例子

输入：

输出：

在检查解决方案时，我发现了这段代码：

谁可以给我解释一下这个。我很清楚在 nlog(n) 中计算 LIS。我无法理解的是这部分：

以及排序背后的原因

我想创建一个函数来打印数字列表中的最大值。

给定一个存储在数组中的 n 个整数序列，描述一种递归算法，以打印出具有最大长度的非递减元素的子序列。子序列可能包含不连续的元素，但它们的排序方式应与原始序列相同。

请帮我 ：（

LIS：最长递增子序列问题是找到给定序列的子序列，其中子序列的元素按从低到高的排序顺序排列

例如：

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

最长的递增子序列是 0、2、6、9、13、15。

我可以使用不同的方式开发 LIS，例如动态编程和记忆技术，但是在特殊情况下，我喜欢使用时间复杂度为O(N^2).

截至我认为使用递归我们无法实现具有时间复杂度的算法O(N^2)。（请纠正我）

但是我从谷歌得到了这个算法

这是算法O(N^2)吗？

你能解释一下吗？

我有以下代码：

我想要做的是以下几点：

我有四个数组：date_new、date_old、data_new和data_old一个名为newList. date_old 和 data_old 具有相同的长度，并且 date_new 和 data_new 也一样。我想遍历日期数组检查是否有相等的日期值。在执行此操作时，我想将 data_old 数组中的每个值复制到 newList。当一个值相等时，我想将此时的值从 data_new 位置复制到列表中。在这里，我OutOfBoundException在第二个 for 循环之后得到了一个。怎么了？

以下代码遍历列表一次并找到 LIS。我不明白为什么 DP 算法应该采用 O(n2)。