问题标签 [subsequence]

例子：

数组如下：-4 -10 -15 - 20 100 -67 47 20和 k = 51

预期输出：

-4 -10 -15 - 20 100

-4 -10 -15 - 20 100 -67 47 20

用 O(n^2) 尝试了蛮力解决方案。任何人都可以提出一个更好的解决方案吗？

我有一个具有许多不同 UniqueID 的数据框，它们也按日期排序。每个 UniqueID 从最旧日期到最新日期排序。我们还有一个名为 steps 的列，从 1 到 4 排序。

每个 UniqueID 的目标是找到第一个步骤的最旧实例，然后是第二个步骤的最旧实例等。某些步骤可能丢失，例如 UniqueID =“B”的第 3 步丢失。在这种情况下，我们跳过第 3 步并继续进行第 4 步。

这是原始数据框。

我们要选择的有效条目是观察 3、6、8、12、14、17。创建此数据框：

我有逻辑和一些伪代码，但不能把它们放在一起。因此，在 UniqueID = "A" 的示例数据帧中，我们首先将数据帧分组：

group_by(UniqueID)

找到 UniqueID = "A" 的最小值并分配给一个变量。

v <- min(Step)返回 1

然后为这一步取索引

i <- which.min(Step)返回 3

然后我们想要找到大于第一步的最小步长，并且只搜索第一步之后出现的元素。所以现在我们只搜索大于 1 的 Step 值，并且只从我们发现的第一个值的位置开始，在这种情况下从观察 3 开始。我们希望对每个 UniqueID 的所有观察重复此操作，直到我们到达最后一个观测值，或者在剩余元素中找不到大于最后一个观测值的观测值。

这是用于创建示例数据框的 dput：

使用 jeremycg 的方法崩溃的替代 dput。

编辑：即使使用来自 jeremycg 的更新代码，UniqueID 的 dput 也会继续崩溃：

我是动态编程的新手，正在阅读最长递增子序列（LIS）问题。

该解决方案表明序列不必像原始数组中那样连续。元素之间可以跳过；但我有另一种印象。

您能否帮助澄清这种困惑。

例如： a = {10,22,9,33,55,66,12,90} LIS 是{10,22,33,55,66,90} => 6

不过，我以为会{33,55,66}

谢谢

下面是解决方案的外观。

输入 Y : 239847239
输入 X : 847
X 是 Y 的子串

输入 Y : 239847239
输入 X : 3923
X 是 Y 的子序列

输入 Y : 239847239
输入 X : 489
X 既不是 Y 的子字符串也不是子序列

以下是我制作代码的粗略尝试：

给定一个正整数数组，我想找出数组中非递减子序列的数量。

例如，如果数组是{6,7,8,4,5,6}，则非递减子序列将是{6},{7},{8},{4},{5},{6},{6,7},{7,8},{4,5},{5,6},{6,7,8},{4,5,6}12 个这样的序列

我将从一个例子开始。假设我们有一个大小为3的数组，其中包含元素a，例如：（其中b和是一些数值）cabc

|1 | 2| 3|
|一个 | 乙| c|

（假设索引从 1 开始，如上例所示）

现在所有可能增加的长度为2的子序列是：

12 23 13

所以需要这些索引处元素的乘积之和，即ab+bc+ac

对于长度3，我们只有一个递增的子序列，即 123，因此abc应该打印。
对于长度4，我们没有序列，因此0打印并且程序终止。

所以给定数组的输出将是：

因此，例如，如果元素a和b分别c是 1、2 和 3，那么输出应该是11,6,0

同样，对于具有元素 a、b、c、d 的大小为4的数组，输出将是：

等等...

现在显然蛮力对于较大的数组大小值来说效率太低了。我想知道是否有一种有效的算法来计算给定大小的数组的输出？

编辑1：我尝试找到一种模式。例如对于大小为4的数组：

The first value we need is :(ab+ac+bc)+d(a+b+c)= ab+ac+ad+bc+bd+cd (Take A=ab+ac+bd) then the second value we need is:(abc) +d(A) = abc+abd+acd+bcd(B=abc) then the third value we need is : (0) +d(B) = abcd(Let's take 0 as C) then the fourth value we need is: +d(C) = 0

但它仍然需要大量计算，我无法找到一种有效的方法来实现它。

编辑2：我的问题与此不同，因为：

1. 我不需要所有可能的排列。我需要从长度 2 到 n+1 的所有可能增加的子序列。
2. 我也不需要打印所有可能的此类序列，我只需要由此获得的值（如上所述），因此我正在寻找一些数学概念或/和一些动态编程方法来有效地解决这个问题。
3. 请注意，我正在根据索引值找到所有可能的此类递增子序列的集合，然后根据上述索引位置处的值进行计算。

我有n 个按固定顺序排列的m个整数数组。我需要找到一个最长递增的子序列，以使子序列中的每个元素都恰好属于其中一个数组。我能比O (n ² ) 做得更好吗？

我希望探索不同的算法，包括递归和动态编程，以检查一个 arrayA 是否是 arrayB 的子序列。例如，

我尝试了一些不同的搜索，但我似乎只能找到计算最长递增子序列的算法。

给定一个数字数组，问题是找到长度为lis-1的递增子序列的总数，其中lis是该给定数组的长度。 Largest Increasing sub-sequence

示例：假设数组是5 6 3 4 7 8. 在这里，lis = 4。所以，lis-1 = 3。因此，子序列的总数8如下：

有人可以给我这个算法的想法，我无法弄清楚。

我想计算给定数组中最长子序列的总和和长度t。

对于1 1 7 3 2 0 0 4 5 5 6 2 1我得到输出的数字：

sum is 20 length is 6

但是对于相同的数字以相反的顺序1 2 6 5 5 4 0 0 2 3 7 1 1我得到输出：

sum is 17 length is 6这不是真的，因为我应该得到sum is 12 length is 5.

有人能发现我的错误吗？