如何高效查找最长递增子序列（LIS）的全部对应子序列？

架构老林

2026-7-2

问题：查找所有最长递增子序列（LIS）的高效优化方案

给定数组序列，需找出所有长度等于最长递增子序列（LIS）长度的递增子序列。例如数组[1, 3, 2, 5, 2]应输出：1 3 5 和 1 2 5。

当前已实现的LIS长度计算函数基于O(nlogn)的动态规划思路，效率极高，但查找所有对应子序列的函数在数组规模达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;
}

查找指定长度递增子序列的函数

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;
}

主函数

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 << '\n';
    }
}

优化方案

核心问题分析

现有getAllIncreasingSubsequences函数的问题在于：它存储了所有可能的递增子序列（无论长度是否接近LIS），当数组规模较大时，子序列数量呈指数级增长，导致时间和空间复杂度爆炸。

优化思路

预处理关键信息：先计算每个位置的dp_len数组，dp_len[i]表示以sequence[i]结尾的最长递增子序列长度，复用原O(nlogn)的LIS计算逻辑即可快速得到。
定向构建LIS：只保留能构成LIS的路径，从后往前逐层构建（从LIS的最后一个元素倒推到第一个元素），避免存储无关子序列。
去重优化：在构建过程中跳过重复元素，避免生成重复的子序列，减少无效计算。

优化后代码实现

1. 同时获取LIS长度和dp_len数组

#include <vector>
#include <utility>
using namespace std;

pair<int, vector<int>> getLISLengthAndDpLen(const vector<int>& sequence) {
    int n = sequence.size();
    vector<int> lisEnd(n + 1, 0);
    vector<int> dp_len(n, 0);
    int length = 0;

    for (int i = 0; i < n; ++i) {
        int low = 1, 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;
        dp_len[i] = pos;
        lisEnd[pos] = i;
        if (pos > length) {
            length = pos;
        }
    }
    return {length, dp_len};
}

2. 高效获取所有LIS

#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

vector<vector<int>> getAllLIS(const vector<int>& sequence, int L, const vector<int>& dp_len) {
    int n = sequence.size();
    vector<vector<int>> result;

    // 分层存储：layers[k] 存储长度为k的LIS前缀（从后往前构建）
    vector<vector<pair<int, vector<int>>>> layers(L + 1);

    // 初始化最后一层（长度为L的前缀，即LIS的最后一个元素）
    for (int i = n - 1; i >= 0; --i) {
        if (dp_len[i] == L) {
            // 去重：同一层相同值的元素只保留一个
            bool duplicate = false;
            for (const auto& p : layers[L]) {
                if (sequence[p.first] == sequence[i]) {
                    duplicate = true;
                    break;
                }
            }
            if (!duplicate) {
                layers[L].emplace_back(i, vector<int>{sequence[i]});
            }
        }
    }

    // 从L-1层到1层，逐层构建完整LIS
    for (int k = L - 1; k >= 1; --k) {
        for (const auto& p : layers[k + 1]) {
            int prev_idx = p.first;
            const vector<int>& curr_subseq = p.second;
            int last_val = sequence[prev_idx];
            unordered_set<int> used_vals; // 记录已使用的元素值，避免重复路径

            for (int j = prev_idx - 1; j >= 0; --j) {
                if (dp_len[j] == k && sequence[j] < last_val) {
                    if (used_vals.count(sequence[j])) {
                        continue;
                    }
                    used_vals.insert(sequence[j]);
                    vector<int> new_subseq = curr_subseq;
                    new_subseq.insert(new_subseq.begin(), sequence[j]);
                    layers[k].emplace_back(j, new_subseq);
                }
            }
        }

        // 对当前层的子序列去重，移除完全相同的前缀
        sort(layers[k].begin(), layers[k].end(), [&](const auto& a, const auto& b) {
            return a.second < b.second;
        });
        auto last = unique(layers[k].begin(), layers[k].end(), [&](const auto& a, const auto& b) {
            return a.second == b.second;
        });
        layers[k].erase(last, layers[k].end());
    }

    // 第一层的所有子序列就是完整的LIS
    for (const auto& p : layers[1]) {
        result.push_back(p.second);
    }
    return result;
}

3. 修改后主函数

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> sequence = {1, 3, 2, 5, 2};
    auto [L, dp_len] = getLISLengthAndDpLen(sequence);
    vector<vector<int>> increasingSubsequences = getAllLIS(sequence, L, dp_len);

    cout << "L: " << L << endl;
    cout << "Increasing subsequences: " << endl;
    for (auto& subsequence : increasingSubsequences) {
        for (auto& element : subsequence) {
            cout << element << " ";
        }
        cout << '\n';
    }
    return 0;
}

优化效果说明

空间优化：仅存储与LIS构建相关的子序列前缀，避免存储所有递增子序列，空间复杂度从指数级降至O(L*M)（M为LIS的数量）。
时间优化：通过dp_len数组快速定位可构成LIS的元素，减少无效遍历；去重逻辑避免重复生成相同子序列，进一步降低计算量。
适配大数组：针对1000+规模的数组，该方案的性能远优于原三层循环实现。

内容的提问来源于stack exchange，提问作者lukakone Konečnik

如何高效查找最长递增子序列（LIS）的全部对应子序列？

现有代码 #

计算LIS长度的函数 #

查找指定长度递增子序列的函数 #

主函数 #

优化方案 #

核心问题分析 #

优化思路 #

优化后代码实现 #