2

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

令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将导致更好的解决方案。

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

4

3 回答 3

1

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

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

一个元素skip[i]包含以 结尾的最长递增子串的长度，i中间跳过单个组。noskip通过在 O(n 2 )中回顾 , 的值，在算法的第二次运行中计算此数组。

数组的最高值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]。的初始值skip[i]设置为skip[i-1]if data[i] > data[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);

演示。

于 2017-06-10T20:44:44.813 回答
1

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

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

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

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

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

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

    （到目前为止，所有这些都是关于原始数组 A 中的子字符串，而不是删除后的数组 C）

  • 使用它，我们可以longestSSAfterB通过查找 BST 中小于该元素的最大元素并将该长度加 1 来找到 C 中以任何元素结尾的最长子字符串（直接跟在某个 B 之后）。

  • 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
于 2017-06-10T22:45:37.970 回答
0

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

对于 A，维护到数组说prefand suff。

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

它们可以在O(n).

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

对于您的示例，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。

于 2017-06-10T20:43:41.483 回答