# 最長遞增子序列的構造（`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; } ```