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