如何用O(n log n)算法获取最长递增子序列（而非仅长度）

原代码里的temp数组只是用来维护最长递增子序列的长度，里面的元素并不是真实的LIS——它会用更小的元素替换已有位置来优化长度计算，所以没法直接从temp拿到实际的子序列。要获取具体的LIS内容，得额外记录每个元素对应的LIS长度，再通过回溯得到真实序列。

实现思路 #

• 新增lengths数组，lengths[i]表示以arr[i]结尾的最长递增子序列的长度。
• 遍历数组时，和原逻辑一样更新temp，同时给lengths[i]赋值：如果元素直接追加到temp末尾，lengths[i]就是temp的新长度；如果是替换temp里的元素，lengths[i]就是替换位置的索引+1（因为索引从0开始）。
• 遍历完成后，拿到LIS的最大长度，从数组末尾往前回溯：找到第一个长度等于当前剩余长度的元素，加入结果列表，剩余长度减1，直到长度为0。最后反转结果列表，就是正确的LIS。

修改后的完整代码 #

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> longestIncreasingSubsequence(int arr[], int n) {
    vector<int> temp;
    vector<int> lengths(n, 0); // 记录每个元素结尾的LIS长度

    temp.push_back(arr[0]);
    lengths[0] = 1;

    for (int i = 1; i < n; i++) {
        if (arr[i] > temp.back()) {
            temp.push_back(arr[i]);
            lengths[i] = temp.size();
        } else {
            int ind = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin();
            temp[ind] = arr[i];
            lengths[i] = ind + 1;
        }
    }

    // 回溯获取真实的LIS
    int current_length = temp.size();
    vector<int> result;
    for (int i = n - 1; i >= 0 && current_length > 0; i--) {
        if (lengths[i] == current_length) {
            result.push_back(arr[i]);
            current_length--;
        }
    }
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    int arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<int> lis = longestIncreasingSubsequence(arr, n);

    cout << "最长递增子序列的内容: ";
    for (int num : lis) {
        cout << num << " ";
    }
    cout << endl;
    cout << "最长递增子序列的长度: " << lis.size() << endl;

    return 0;
}

关键说明 #

• lengths数组标记了每个元素在LIS中的“层级”，比如长度为3的元素，说明它是某个长度为3的递增子序列的结尾。
• 从后往前回溯能保证拿到的是最后出现的对应长度的元素，反转后得到的是一个合法的LIS（如果存在多个LIS，这个方法会得到其中一个）。
• 整体时间复杂度还是O(n log n)：遍历数组是O(n)，每次lower_bound是O(log k)（k为当前temp的长度，最大为n），回溯是O(n)，总复杂度不变。

内容的提问来源于stack exchange，提问作者noobcodermousey