c++ - 排列中的升序子序列

Question

给定排列 1...n 例如 5 3 4 1 2 如何在线性时间内找到所有长度为 3 的升序子序列？

是否有可能找到其他长度为 X 的升序子序列？ X

我不知道如何在线性时间内解决它。

Answer 1

您需要实际的升序吗？或者只是上升子序列的数量？

要在列出它们的时间内生成它们是不可能的。正如已经指出的那样，它是 O(N<sup>X</sup> / (X-1)!) . (可能有一个意外因素 X，因为它需要时间 O(X) 来列出大小为 X 的数据结构。)对它们的明显递归搜索与此相差不远。

但是可以及时计算它们 O(X * N<sup>2</sup>)如果你使用动态规划。这是 Python。

counts = []
answer = 0
for i in range(len(perm)):
    inner_counts = [0 for k in range(X)]
    inner_counts[0] = 1
    for j in range(i):
        if perm[j] < perm[i]:
            for k in range(1, X):
                inner_counts[k] += counts[j][k-1]
    counts.add(inner_counts)
    answer += inner_counts[-1]

例如3 5 1 2 4 6和 X = 3你会得到:

counts = [
    [1, 0, 0],
    [1, 1, 0],
    [1, 0, 0],
    [1, 1, 0],
    [1, 3, 1],
    [1, 5, 5]
]
answer = 6

(以上只找到5个，少了一个2 4 6。)

扩展这个答案来创建一个数据结构并不难，它可以很容易地直接列出它们，找到一个随机的等等。