查找长度为 LIS 的子序列最省时的方法是什么？

Question

给定一个数组（向量）序列。 我需要一种方法或修复可能会找到具有最长递增序列长度的所有递增子序列。 例如： [1, 3, 2, 5, 2] 应该输出： 1 3 5 和 1 2 5

1 3 5 是第一个 LIS 长度 3。 那么下一个是 1 2 5.

我已经实现了一些适用于较小实例的东西，但是一旦我有一个更大的序列数组（大小：1000+），程序就会永远运行。

这是我的 LIS 长度函数：它使用动态规划并且工作速度非常快

int findLISLength(const std::vector<int>& sequence, size_t n) {
    std::vector<int> lisEnd(n + 1, 0);
    std::vector<int> parent(n, 0);
    int length = 0;

    for (int i = 0; i < n; ++i) {
        int low = 1;
        int high = length;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (sequence[lisEnd[mid]] < sequence[i])
                low = mid + 1;
            else
                high = mid - 1;
        }
        int pos = low;
        parent[i] = lisEnd[pos - 1];
        lisEnd[pos] = i;

        if (pos > length)
            length = pos;
    }

    return length;
}

这是我的函数，用于查找给定长度的所有递增子序列。 这就是时间复杂度非常高的地方，因为三个 for 循环。 我也尝试过递归，并且需要同样多的时间。

std::vector<std::vector<int>> getAllIncreasingSubsequences(const std::vector<int>& sequence, size_t length) {
    std::vector<std::vector<int>> result;
    std::vector<std::vector<std::vector<int>>> dp(sequence.size());

    for (size_t i = 0; i < sequence.size(); ++i) {
        dp[i].push_back({ sequence[i] });
        for (size_t j = 0; j < i; ++j) {
            if (sequence[i] > sequence[j]) {
                for (const auto& subseq : dp[j]) {
                    if (subseq.size() + 1 <= length) {
                        auto newSeq = subseq;
                        newSeq.push_back(sequence[i]);
                        dp[i].push_back(newSeq);
                    }
                }
            }
        }
    }

    for (const auto& subseq : dp) {
        for (const auto& sub : subseq) {
            if (sub.size() == length) {
                result.push_back(sub);
            }
        }
    }

    return result;
}

我从文件中读取序列号，然后调用函数。 序列是： [43629 88099 89706 22748 1174 68526 8869 61079 64279 2965 56809 3540 94669 72740 94999 18126，...]

int main(){
size_t L = findLISLength(sequence, N);
vector<vector<int>> increasingSubsequences = getAllIncreasingSubsequences(sequence, L);
//print subsequence
cout << "L: " << L << endl;
cout << "Increasing subsequences: " << endl;
for (auto& subsequence : increasingSubsequences) {
    for (auto& element : subsequence) {
     cout << element << " ";
    }
    cout << endl;
}
}

Answer 1

我无法弄清楚你的代码是如何工作的，所以我决定以一种对我来说既清晰又相当有效的方式重写。如果答案是从长度为

m

的列表中增加长度为

k

的序列，我的算法将是

n

。请注意，

O(n^2 + m*k)

可以随着向量的大小呈指数增长。最坏的情况是具有结构

m

的向量，那么将有

[2, 1, 4, 3, 6, 5, 8, 7, ..., n, n-1]

最大递增序列。增加序列的数量几乎肯定是您的代码太慢的原因。这就是为什么我边走边打印。前两行就可以告诉我们情况会有多糟糕。这是一个演示程序。

2^(n/2)