带间隙的最长递增子串

Question

我遇到了如下指定的问题：

设A为正整数序列。
让 B 成为 A.
的子串设 C 是通过从 A.
中删除 B 创建的序列对于给定的 A，找到 C 的最长递增（严格）子串的长度，其中 B可以任意选择。

例如让A = [3 2 5 7 1 2 8 1]。如果我们设置 B = [1 2]，则 C = [3 2 5 7 8 1] 其最长递增子串为 [2 5 7 8]，长度为 4。4 是答案，因为不存在其他 B 会导致更好的解决方案。

我找不到解决问题的算法（当然是多项式时间:)），但我相信这将是最长递增子序列问题的一些变体。
请帮我找到一个好的算法或者给我一些提示或参考。

Answer 1

我对这个问题了解不多，但我认为这个 O(nlogn) 解决方案会奏效。

对于 A，维护数组说 pref 和 suff。

pref[i] 包含您可以从 i 开始创建的最长递增子数组 (LIS)。同样，suff[i] 包含您可以创建的以 i.

结尾的 LIS

它们可以在 O(n) 中创建。

然后找到(i,j)的最优组合，使得suff[i] + pref[j]最大，i<j and arr[i]<arr[j]。这可以通过遍历每个 i 并通过将 pref 数组存储为 bst 来找到每个 j 来找到。

例如，A = [3 2 5 7 1 2 8 1]。

然后，

3 2 5 7 1 2 8 1 (arr)
1 1 2 3 1 2 3 1 (suff)
1 3 2 1 3 2 1 1 (pref)

如你所说删除 1,2 得到 suff[3] + pref[6] = 3 + 1 = 4。

Answer 2

制作两个长度为 n 的辅助数组 - noskip 和 skip.

元素 noskip[i] 包含以 i 结尾的最长递增子串的长度，没有从原始字符串中删除任何内容。在 O(n) 算法的第一遍中计算此数组。

一个元素skip[i]包含以i结尾的最长递增子串的长度，中间有一个单组的跳过。通过在 O(n²).

中回顾 noskip 的值，在算法的第二个运行中计算此数组

skip 数组的最大值就是您问题的答案。

下面是两个数组如何查找您的输入：

data:   3 2 5 7 1 2 8 1
noskip: 1 1 2 3 1 2 3 1
skip:   1 1 2 3 1 2 4 1

当我们查看 8 时，我们遍历 data，寻找满足 j < i、data[j] < data[i] 和 noskip[j]+1 > skip[i] 的元素。如果 data[i] > data[i-1]，skip[i] 的初始值设置为 skip[i-1]，否则设置为 1。

这是 Java 中的示例实现：

int[] data = new int[] {3, 2, 5, 7, 1, 2, 8, 1};
int[] noskip = new int[data.length];
int[] skip = new int[data.length];
noskip[0] = 1;
for (int i = 1 ; i != skip.length ; i++) {
    noskip[i] = data[i] > data[i-1] ? noskip[i-1]+1 : 1;
}
skip[0] = 1;
int res = 1;
for (int i = 1 ; i != data.length ; i++) {
    skip[i] = data[i] > data[i-1] ? skip[i-1]+1 : 1;
    for (int j = i-1 ; j >= 0 ; j--) {
        if (data[j] < data[i] && noskip[j]+1 > skip[i]) {
            skip[i] = noskip[j]+1;
        }
    }
    res = Math.max(res, skip[i]);
}
System.out.println(res);

Demo.

Answer 3

在对输入数组进行单次迭代时：

设置一个数组smallest[n]，其中smallest[i]表示长度为i的递增子串可以结束的最小元素（例如如果smallest[3] = 5，这意味着有长度为3的子串以5结尾，并且没有长度为3的子串以4结尾，否则smallest[3]将是4 ).

我们可以跟踪到目前为止最长的子串 i，如果该元素大于当前元素，则简单地替换 smallest[i]。

关于这个数组的一个重要说明：这个数组中的元素将严格按照递增顺序排列，也就是说，如果数组中存在以元素x结尾的长度为i的子串数组中，不再有包含等于或小于 x 的元素的子字符串（这是因为较长的子字符串将包含长度为 i 且以小于 x 的元素结尾的子字符串，因此 smallest[i] 将是该元素而不是 x).
除了这个数组，还保留一个二叉搜索树（BST），将元素映射到子字符串长度（本质上与数组相反）。

更新smallest时，也从BST中删除旧元素并插入新元素。

（到目前为止所有这些都是关于原始数组 A 中的子字符串，而不是数组 post-删除 C）
使用这个，我们可以通过在 BST 中查找小于该元素的最大元素来找到 C 中以任何元素结尾（直接跟在某个 B 之后）的最长子串 longestSSAfterB将该长度加 1。
C 中以任何给定元素结尾的最长子串将只是 1 + 以前一个元素结尾的最长子串的最大值（如果较小，则为 0）和 longestSSAfterB .

C 中最长的子串就是我们在上面找到的最长子串。

所有这些都需要 O(n log n)。

示例：

A = [3 2 5 7 1 2 8 1]
                   BST.floor(i)+1
        currentSS  longestSSAfterB  longestSSinC  smallest BST
A[0]=3  1          0+1=1            max(1,0+1)=1  [3]      [(3→1)]
A[1]=2  1          0+1=1            max(1,0+1)=1  [2]      [(2→1)]
A[2]=5  2          (2→1)->1+1=2     max(2,1+1)=2  [2,5]    [(2→1), (5→2)]
A[3]=7  3          (5→2)->2+1=3     max(3,2+1)=2  [2,5,7]  [(2→1), (5→2), (7→3)]
A[4]=1  1          0+1=1            max(1,0+1)=1  [1,5,7]  [(1→1), (5→2), (7→3)]
A[5]=2  2          (1→1)->1+1=2     max(2,1+1)=2  [1,2,7]  [(1→1), (2→2), (7→3)]
A[6]=8  3          (7→3)->3+1=4     max(4,2+1)=4  [1,2,7]  [(1→1), (2→2), (7→3)]
A[7]=1  1          0+1=1            max(1,0+1)=1  [1,5,7]  [(1→1), (5→2), (7→3)]

Longest substring = max(longestSSinC) = 4

带间隙的最长递增子串

Longest increasing substring with gap

algorithm

substring

lis