确定数组中的哪些项是最长递增子序列的一部分
这是最长增子序列问题的一种变体。假设您不是想要找到一个序列，也不是想要计算有多少序列，而是想要识别可以是某个最长递增序列的一部分的项。
例如，在列表1,2,4,3,0,5中，除零之外的所有项都可以是最长递增子序列的一部分。
找到这些物品的策略是什么？能做到的效率有多高？
共有1个答案
一种方法是使用与最长递增子序列问题相同的动态算法，在假定i是最后一个项目的情况下，跟踪排在第一个项目之前的最佳项目，但对其进行调整以跟踪联系。然后，在每个项目的最佳前项已知之后，确定当从得分最高的项目开始时，哪些项目可以通过该图到达。
在示例1,2,4,3,0,5中,它的工作方式如下：
1在索引0处，因此在没有前一个索引的情况下给它一个lis分数为12前面可以有1，因此2获得1+1=2的lis分数和0 的前一个索引
4前面可以有2和1，但2具有更好的lis分数，因此4获得2+1=3的lis分数和1 的前一个索引
3前面还可以有2和1，并且2具有更好的lis分数，因此3获得2+1=3的lis分数和1 的前一个索引
0前面不能有任何内容，因此它在没有前一个索引的情况下获得1的lis分数5前面可以有任何其他项，但3和4具有最好的lis分数(=3)，因此5获得的lis分数为3+1=4，前面的索引为2或3。
现在，我们使用得分最多的项目，在本例中仅5，并迭代地向后搜索它之前的项目。这将把5、3、4、2和1（但不是0)标记为can-be-in-long-sequence。
这肯定是在O(n^2)时间内运行的，我认为通过巧妙的操作，它可以在O(n lg n)时间内运行。
从二次时间开始的主要挑战是，不是制作一个显式的图，图中“最优地位于”边之前。像1,1,1,1,1,1,1,...,2,2,2,2,2,2,2,...这样的列表有一个二次方数的边，因此您需要避免将它们全部存储或全部探究。
-
假设我们有一些不相交的递减序列： 我选择一些递减序列（例如按顺序,,,,的5个递减序列）并将它们级联（结果序列。 现在我想求S中最长递增子序列的长度，在上面的示例中:-> 预期时间复杂度小于O(S)。
-
最长增子序列是我们熟知的问题，我用耐心算法给出了一个解决方案。 我曾想过先用我的算法，然后找到长度为N的第一个序列，但不知道该怎么做。 那么，如何从随机整数序列中找到第一个最长的递增子序列呢？ 我的代码段： 我的代码返回：1 2 8 第一个序列是：3 6 8 另一个例子： 我的代码正确返回：1 2 3 基本上，只要第一个最长序列与最佳最长序列相同，我的代码就能工作。但是当你有一堆相同长度的最长序列
-
我在阅读了允许K个异常的最长递增子序列后创建了这个线程。我意识到提问的人并没有真正理解这个问题，因为他指的是一个链接，该链接解决了“允许一次更改的最长递增子数组”问题。所以他得到的答案实际上与李的问题无关。 假设给定一个长度为N的数组A。查找允许K个异常的最长递增子序列。 示例：N=9，K=1 A=[3,9,4,5,8,6,1,3,7] 答案：7 说明： 最长递增子序列为：3,4,5,8（或6），
-
我为最长的递增子序列生成了以下代码： 输入：nums=[10,9,2,5,3,7,101,18] 输出：4 说明：最长的递增子序列是[2,3,7,101]，因此长度为4。 有人能帮我理解这句话吗 三个点的意义是什么？正如我们所知，映射生成键值对，映射与切片一起做什么？
-
在最多一个序列存在重复的情况下，可以将最长公共子序列问题转化为最长递增子序列问题。减少问题的过程说明在这里： 假设您有以下序列： 然后，创建一个整数序列S3，其中您必须将S2的每个元素的位置放在S1中（如果元素在S1中不存在，那么忽略那个元素）。在本例中： 这种方法是如何工作的？为什么这种约简解决了寻找最长公共子序列的问题？
-
我正在解决一个程序设计的挑战，在一个2D NxN矩阵中寻找最长的递增子序列的长度。在序列的每个元素中，行和列都必须增加（不需要连续）。本文用动态规划方法求解，但它是O(n^4)，效率低。然而，在O(n^3)中有许多解。一种这样的解决办法是： 有人能解释一下它的工作原理或其他O(n^3)方法吗？我根本听不懂：（。