给定序列中所有增加的子序列的数量？

Question

你可能听说过一个众所周知的问题,那就是找到增长最快的子序列.最优算法具有O(n*log(n))复杂性.

我正在考虑在给定序列中找到所有增加的子序列的问题.我找到了一个问题的解决方案,我们需要找到一些长度为k的增加子序列,这些子序列具有O(n*k*log(n))复杂性(其中n是序列的长度).

当然,这个算法可以用于我的问题,但O(n*k*log(n)*n) = O(n^2*k*log(n))我认为解决方案具有复杂性.我认为,必须有更好的(我的意思是 - 更快)解决方案,但我还不知道.

如果您知道如何解决在给定序列中以最佳时间/复杂度找到所有增加的子序列的问题(在这种情况下,最佳=优于O(n^2*k*log(n))),请让我知道这一点.

最后:这个问题不是功课.在我的演讲中提到了一个增长最长的子序列的问题,我开始考虑给定序列中所有增加的子序列的一般概念.

Answer 1

我不知道这是否是最佳的 - 可能不是,但这是一个DP解决方案O(n^2).

让 dp[i] = number of increasing subsequences with i as the last element

for i = 1 to n do
    dp[i] = 1
    for j = 1 to i - 1 do
        if input[j] < input[i] then
            dp[i] = dp[i] + dp[j] // we can just append input[i] to every subsequence ending with j

那么这只是总结所有条目的问题 dp

Answer 2

您可以在O(n log n)时间内计算增加子序列的数量,如下所示.

回想一下最长增长子序列长度的算法:

对于每个元素,计算先前元素中的先前元素,并将该元素添加到该长度.

如果使用像平衡二叉搜索树这样的数据结构计算前驱,那么该算法在O(n ^ 2)时间内运行,并在O(n log n)中运行(或者在整数的情况下甚至更好). BST)(或类似于整个面包车的van Emde Boas树更高级的东西).

为了修改该算法以计算序列的数量,在每个节点的BST中存储以该元素结束的序列的数量.处理列表中的下一个元素时,只需搜索前一个元素,计算以小于当前正在处理的元素的元素结束的序列数(在O(log n)时间内),并将结果存储在BST以及当前元素.最后,总结树中每个元素的结果以获得结果.

需要注意的是,增加序列的数量可能非常大,因此算法不再需要每次操作O(1)次.这需要考虑在内.

伪代码:

ret = 0
T = empty_augmented_bst() // with an integer field in addition to the key
for x int X:

  // sum of auxiliary fields of keys less than x
  // computed in O(log n) time using augmented BSTs
  count = 1 + T.sum_less(x)

  T.insert(x, 1 + count) // sets x's auxiliary field to 1 + count
  ret += count // keep track of return value

return ret

Answer 3

我假设在不损失泛化性的情况下，输入 A[0..(n-1)] 由 {0, 1, ..., n-1} 中的所有整数组成。

设 DP[i] = 以 A[i] 结尾的递增子序列的数量。

我们有重现：

为了计算 DP[i]，我们只需要计算所有 j 的 DP[j]，其中 A[j] < A[i]。因此，我们可以按 A 值的升序计算 DP 数组。对于所有 k，其中 A[k] > A[i]，DP[k] = 0。

问题归结为计算 DP[0] 到 DP[i-1] 的总和。假设我们已经计算了 DP[0] 到 DP[i-1]，我们可以使用 Fenwick 树在 O(log n) 中计算 DP[i]。

最终答案是 DP[0] + DP[1] + ... DP[n-1]。该算法的运行时间为 O(n log n)。