带间隙的最长增长子串

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.

我找不到解决这个问题的算法(当然是在多项式时间: )，但我相信这将是最长增长子序列问题的一些变化。

请帮助我找到一个好的算法，或给我一些提示或参考。

Answer 1

在通过输入数组进行一次迭代时：

• 设置一个数组smallest[n]，其中smallest[i]表示长度不断增加的i子字符串可以以其结尾的最小元素(例如，如果是smallest[3] = 5，这意味着有一个长度3的子字符串以5结尾，并且没有长度3的子字符串以4结尾，否则smallest[3]将是4)。 到目前为止，我们可以跟踪最长的子字符串i，如果该元素大于当前元素，则只需替换该元素即可。 有关此数组的一个重要注意事项:该数组中的元素将按严格的递增顺序排列，也就是说，如果数组中存在长度为i的以元素x结尾的子字符串，则不再存在包含等于或小于x的元素的子字符串(这是因为较长的子字符串将包含长度小于x的子字符串，因此smallest[i]将是该元素而不是x)。
• 除了这个数组，还保留一个二进制搜索树(BST)，它将元素映射到子字符串长度(本质上与数组相反)。 更新smallest时，也要从BST中删除旧元素并插入新元素。 (到目前为止，所有这些都是关于原始数组A中的子字符串，而不是删除后C的数组)
• 使用此方法，我们可以找到C中最长的子字符串longestSSAfterB，以任何元素结尾(直接跟随某个B)，方法是查找比BST中的最大元素更小的元素并将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

Answer 2

我对这个问题不太了解，但我认为这个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来查找每个pref。

举个例子，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将给出suff3 + pref6 =3+1= 4。