# 最长递增子序列的构造（`N log N`） > 原文： [https://www.geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/](https://www.geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/) 在上一篇文章中，我详细解释了最长[增加子序列](https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/)（LIS）问题。 但是，该帖子仅涵盖了与 LIS 查询大小有关的代码，而没有涵盖 LIS 的构造。 我把它留作练习。 如果您解决了，那就加油。 如果不是，那么您并不孤单，这里是代码。 如果您尚未阅读我的上一篇文章，请在处阅读[。 请注意，以下代码以相反的顺序打印 LIS。 我们可以使用堆栈（显式堆栈或系统堆栈）修改打印顺序。 我将解释作为练习（简单）进行。](https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/) ## C++ ```cpp // C++ implementation to find longest increasing subsequence // in O(n Log n) time. #include <bits/stdc++.h> using namespace std; // Binary search int GetCeilIndex(int arr[], vector<int>& T, int l, int r,                  int key) {     while (r - l > 1) {         int m = l + (r - l) / 2;         if (arr[T[m]] >= key)             r = m;         else             l = m;     }     return r; } int LongestIncreasingSubsequence(int arr[], int n) {     // Add boundary case, when array n is zero     // Depend on smart pointers     vector<int> tailIndices(n, 0); // Initialized with 0     vector<int> prevIndices(n, -1); // initialized with -1     int len = 1; // it will always point to empty location     for (int i = 1; i < n; i++) {         if (arr[i] < arr[tailIndices[0]]) {             // new smallest value             tailIndices[0] = i;         }         else if (arr[i] > arr[tailIndices[len - 1]]) {             // arr[i] wants to extend largest subsequence             prevIndices[i] = tailIndices[len - 1];             tailIndices[len++] = i;         }         else {             // arr[i] wants to be a potential condidate of             // future subsequence             // It will replace ceil value in tailIndices             int pos = GetCeilIndex(arr, tailIndices, -1,                                    len - 1, arr[i]);             prevIndices[i] = tailIndices[pos - 1];             tailIndices[pos] = i;         }     }     cout << "LIS of given input" << endl;     for (int i = tailIndices[len - 1]; i >= 0; i = prevIndices[i])         cout << arr[i] << " ";     cout << endl;     return len; } int main() {     int arr[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };     int n = sizeof(arr) / sizeof(arr[0]);     printf("LIS size %d\n", LongestIncreasingSubsequence(arr, n));     return 0; } ```