algorithm - 带间隙的最长递增子串

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

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

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

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

  关于这个数组的一个重要说明:这个数组中的元素将严格按照递增顺序排列，也就是说，如果一个长度为 i 的子串以元素 x 结尾> 存在于数组中，不再有包含元素等于或小于 x 的子字符串(这是因为较长的子字符串将包含长度为 i 的子字符串，结尾为小于 x 的元素，因此 smallest[i] 将是该元素而不是 x)。

• 除了这个数组之外，还保留一个二叉搜索树 (BST)，将元素映射到子串长度(本质上与数组相反)。

  更新 smallest 时，同样从 BST 中移除旧元素并插入新元素。

  (到目前为止所有这些都是关于原始数组 A 中的子字符串，而不是数组删除后的 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