我遇到了一个指定为以下的问题：
设a为正整数序列。
设B是a的子串。
设C是通过从a中删除B而创建的序列。
对于给定的a，求c的最长递增（严格）子串的长度，其中b可以任意选择。
例如，让a=[3 2 5 7 1 2 8 1]。如果我们设置b=[12]，那么c=[3 2 5 7 8 1]，其最长的递增子串是[2 5 7 8]，长度是4。4是答案，因为没有其他B会导致更好的解决方案。
我找不到一个算法来解决这个问题（在多项式时间内，当然：），但我相信这是最长增长子序列问题的一些变体。
请帮助我找到一个好的算法或给我一些提示或参考。
最佳答案
在对输入数组执行单个迭代时：
设置数组smallest[n]，其中smallest[i]表示长度i的递增子串可以结束的最小元素（例如，如果smallest[3] = 5，则表示有一个长度为3的子串以5结尾，并且没有长度为3的子串以4结尾，否则smallest[3]将是4）。
我们可以跟踪到目前为止最长的子串i，如果该元素大于当前元素，则只需替换smallest[i]。
关于这个数组的一个重要注释：这个数组中的元素将严格地增加，也就是说，如果数组中的长度i结尾元素[cc]中存在数组，则不再有包含等于或小于x的元素的子串（这是因为较长的子串将包含长度子集x）。以小于i的元素结尾，因此x将是该元素，而不是smallest[i]）。
除了这个数组，还要保留一个二进制搜索树（bst），它将元素映射到子字符串长度（基本上与数组相反）。
当更新x时，也从bst中删除旧元素并插入新元素。
（到目前为止，所有这些都是关于原始数组A中的子字符串，而不是删除后的数组C）
使用这个，我们可以通过查找BST中小于该元素的最大元素并将1添加到该长度中，找到C中以任何元素结尾的最长子字符串smallest（直接在某些B之后）。
在任何给定元素结束的C中最长的子串将是最大的1 +最长的子串在前一个元素中结束（如果它更小，否则0）和longestSSAfterB。
C中最长的子串就是我们在上面找到的最长的子串。
所有这些都需要longestSSAfterB。
例子：
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