问题标签 [subsequence]

给定一个包含 N 个不同整数的数组，找到满足的最长子序列：

1. 子序列的起始元素是子序列的最小元素。
2. 子序列的结束元素是子序列中最大的。

例如：8,1,9,4,7。答案是 1,4,7。

2,6,5,4,9,8。答案是 2,6,5,4,9 或 2,6,5,4,8。

这是一个O(N^2)算法：

• 设X为数字数组。
• 迭代X。假设我们在 index i。设Y为数组，其中 Y[j] 是(j, i]小于 X[j] 的元素数。设为小于 X[i]z的元素个数。[j, i]如果 X[j] 小于 X[i]，我们可以得到一个满足约束的长度为 zY[j] 的子序列。

• 设置z为1。j从i-1下循环到0.

  if X[j] < X[i]: z++; ans = max(ans, z - Y[j]); else Y[j]++;

我们能做得更好吗？我认为应该有一个O(NlogN)算法来找到最大长度。

我有一个场景，我需要生成以下格式的批号（主键）。

批号： ( XX ) ( XXXXX ) 位置顺序

每个批次的序列从 00001 开始。但是，我们不能有一个序列号生成器来执行此操作。我脑海中可能的解决方案是：

1. 创建一个包含数字的额外表。但是有可能多个用户获得相同的序列，因为可能存在未提交的事务。
2. 每次保存实体时，我们都会从该列中获取 max(substring(batchnum,2)) 并添加 +1。但这会对性能造成非常巨大的过载，并且还会出现多个用户获得相同序列的问题。

我试图找到一个字符串的所有可能的子序列。例如这个字符串中的“abc”，我们将找到总共 8 个字符串 2^3=8 个组合。像 a, b, c, ab, ac, bc, abc '\0'。但我的代码只打印字符串的所有字符。我怎样才能做到这一点？

这是我的问题：

编写一个程序distance(List, Nemptylist, SubList)/3，检查是否Sublist 是一个子列表，List其距离不超过N项之间的约束（N 实现为Nemptylist-N匿名变量列表）。假设它List 是完全实例化的。允许重复答案，只要它们的数量是有限的。

例如，对于N= 2 ：

我已经坐了几个小时，试图解决这个问题，最终上面的例子奏效了，但后来我运行了一些测试，但它们失败了。

我现在的解决方案如下：

当我尝试运行此测试时：

由于超出运行时间错误而失败。

我调试了几个小时，我真的筋疲力尽了。请帮我完成这个可怕的任务。

假设我们有一个包含 n 个实数的数组。我们想在数组中找到最长的连续子序列，它的总和大于或等于零。

它必须在线性时间内完成。

我们实际上不知道如何开始回答这个问题。

提前致谢。

下面是使用递归编写的用于解决最大子序列问题的 C++ 示例代码 - 不完全是子序列，而是最大子序列的总和。

如果剩下的单个元素是负数，为什么基本情况必须返回 0？如果我们返回更高的值 0 而不是实际的负值，它不会影响总和吗？我在互联网上搜索了基本案例和问题陈述的解释，但找不到解释。

我知道 subSequence 返回一个只读的 charSequence。此外，String 类实现了 CharSequence。subString 返回一个字符串。

但是，在子序列和子字符串中，何时以及更喜欢哪一个

有一个 leetcode 问题：不同的子序列。

给定一个字符串 S 和一个字符串 T，计算 S 中 T 的不同子序列的数量。一个字符串的子序列是一个新的字符串，它是从原始字符串中删除一些（可以是无）字符而不干扰其余字符的相对位置。（即，“ACE”是“ABCDE”的子序列，而“AEC”不是）。

下面是一个例子：S = "rabbbit", T = "rabbit" 返回 3。

我的问题：

在这里，我不明白“计算S中T的不同子序列的数量”是什么意思 我认为“r”，“ra”，“b”rab”，“rabt”等都是T的子序列，而且它们也在S中。但是返回给出的答案是“3”。所以，我一定是误解了这个问题，有人能给我解释一下吗？只是给我一些更典型的例子和解释就可以了，不要告诉我如何解决它，我希望将其作为练习。在此先感谢

整数序列在线百科全书支持搜索包含您的查询作为子序列的序列，例如。搜索subseq:212,364,420,428将返回8*n+4序列。（http://oeis.org/search?q=subseq:212,364,420,428）

这个惊人的功能显然是由 Russ Cox 和http://oeis.org/wiki/User:Russ_Cox/OEIS_Server_Features实现的，但没有具体说明这是用什么算法实现的。

我想知道它是如何完成的。显然，每次搜索都要经过近一百万个序列对于搜索引擎来说是不切实际的。仅仅保留第一个数字的索引（这就是 Russ Cox 所做的 Google Code Regex Search 的方式）并强制其余的数字也行不通，因为0几乎所有序列中都有类似的数字。事实上，一些查询喜欢0 1匹配整个数据库的很大一部分，所以算法需要一个对所需输出大小敏感的运行时间。

有谁碰巧知道这个功能是如何实现的？

给出了主要的 DNA 序列（一个字符串）（比如说 string1）和另一个要搜索的字符串（比如说 string2）。您必须在 string1 中找到最小长度窗口，其中 string2 是子序列。
string1 = "abcdefababaef"
string2 = "abf"

我想到但似乎不起作用的方法：
1. 使用最长公共子序列（LCS）方法并检查（LCS 的长度 = string2 的长度）。但这会给我 string2 是否作为子序列存在于 string1 中，但不是最小的窗口。
2. KMP 算法，但不知道如何修改它。
3. 准备string2 中string1 的{characters: pos of characters} 的映射。喜欢： { a : 0,6,8,10
b : 1,7,9
f : 5,12 }
然后一些方法来找到最小窗口并仍然保持“abf”的顺序

我不确定我是否在思考正确的方向，或者我完全偏离了方向。
有没有已知的算法，或者有人知道任何方法吗？请建议。
提前致谢。