问题标签 [subsequence]

给定一个整数元素序列S，我需要一个函数来找到索引 i 和索引 j （包括两者）之间的序列的最小元素，使得：nmin(i,j)

1. 初始化需要O(n);
2. 内存空间O(n)；
3. min(i,j)需要O(log(n)).

请为此提出一个算法。

我一直在尝试解析 JSON 文件。它有点不符合结构，所以，为了进入一个结构，我正在使用该文件的子序列（以便它进入一个结构）。但是当我使用子序列或子字符串时，它只是省略了开始（第一个偏移）而不是结束偏移（结束原样）。这是代码：

我也尝试过计算字符然后设置结束偏移量，但它仍然省略了超过指定的字符。

我在一个处理子序列的编码挑战网站上遇到了一个问题。

给定一个整数元素数组，这个数组的子序列是数组中的一组连续元素（即：给定数组v：[7, 8, -3, 5, -1]，v的子序列是8， -3, 5)

你的任务是编写一个函数，找到满足以下条件的数组的左子序列和右子序列：

1. 两个子序列必须是唯一的（它们没有共享元素）

2. 右子序列元素之和与左子序列元素之和之差最大

3. 将差异打印到标准输出 (stdout)

该函数接收array，它是一个整数数组。

数据限制：

1. 该数组至少有 2 个，最多 1,000,000 个数字

2. 数组中的所有元素都是以下范围内的整数：[-1000, 1000]

例子

在上面的例子中，左子序列是[-5, 1, -2]，右子序列是[8,-2,3]

这是我尝试过的

但看起来这不起作用。

我正在尝试编写一个最大子序列乘积程序，该程序基于最大子序列和程序的递归解决方案（也就是说，它将遵循相同的格式）。

到目前为止，它适用于所有情况，除了那些结果应该为“0”的情况，以表明序列中没有产品是正的。对于我下面的五个序列，它适用于除最后一个之外的所有序列：

这是递归方法，其中a是序列，p1最初是a[0]，p2是a[last index]：

关于“checkForSplit”的注释，除非 a[i] == 0，否则该值为 0，并且我们正在检查当前子序列中最左边或最右边的索引，在这种情况下，它被设置为 1。这会触发不同的 ' max3' 其中 PL 不乘以 PR，逻辑是如果 PL 或 PR 为 0，则两者中的另一个可能不是，在这种情况下，它们不应相乘。

正如我所说，该算法适用于除第 5 个序列之外的所有序列。

有任何想法吗？

我知道如何使用动态编程来解决给定两个字符串查找最长公共子序列或最长公共子串的问题。但是，我很难找到解决字符串 X 的最长子序列（字符串 Y 的子串）的问题的解决方案。

这是我的蛮力解决方案：

1. 找到字符串 X 的所有子序列，并按长度 desc 对它们进行排序；
2. 遍历排序后的子序列，如果当前子序列是 Y 的子串，则返回子序列。

它可以工作，但运行时间可能很糟糕。假设 X 中的所有字符都是唯一的，那么有 2^m 个子序列，其中 m 是 X 的长度。我认为检查字符串是否是 Y 的子字符串需要 O(n)，其中 n 是 Y 的长度。所以总运行时间为 O(n*2^m)。

是否有更好的方法来做到这一点，可能通过 DP？

编辑：

这是我要解决的示例：

答案是“ACD”，因为“ACD”是X 的最长子序列，也是Y 的子串。

我在子数组、子序列和子集之间有点困惑

如果我有{1,2,3,4}

然后

子序列可以是{1,2,4}OR{2,4}等。所以基本上我可以省略一些元素但保持顺序。

子数组将是（例如大小为 3 的子数组）

那么子集会是什么？

我对这3个有点困惑。

为什么 subsequence(a,b).toString()比substring(a,b) 快？当我将所有子序列转换为子字符串时，它一直减慢到 %7。为什么会这样？以下是我的代码；

给定 2 个字符串，我们必须找到一个长度最小的字符串，使得给定的字符串是该字符串的子序列。换句话说，我们需要找到一个字符串，以便删除一些字符会产生给定的字符串。一直在想蛮力和LCS，但徒劳无功。

12345 和 11234 应该导致 112345 WWA 和 WWS 有一个答案 WWAS

LCS 的内存效率非常低（DP 之一），蛮力只是幼稚。我应该怎么办？

将序列的位移定义为最大和最小元素之间的差。给定一个整数序列，找出所有长度为 的连续子序列的最大位移m。

例如，如果我们的序列是 [1, 5, 7, 0, 2, -4] 并且 m = 3，

• [1, 5, 7] 的位移为 6。
• [5, 7, 0] 的位移为 7。
• [7, 0, 2] 的位移为 7。
• [0, 2, -4] 的位移为 6。
• 所以最大位移是7。

如果我们让 n 表示输入序列的长度，那么我下面的解决方案在 O(nlog(m)) 时间内运行。有没有办法做得更好？我觉得我必须缺少一个线性时间算法。就这个问题而言，我只关心渐近时间复杂度。

二次最大连续子序列和算法

我想知道是否有人可以解释该算法的工作原理？我擅长 for 循环，我只是不擅长嵌套循环。每次第 8 行的外部 for 循环运行时，“thisSum”总是 0 还是静态的？

非常感谢！我正在努力理解算法。请帮我！我真的很感激时间和精力。