最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。
实现
有两种，时间複杂度分别为O(n^2)与O(n log n)，空间複杂度均为O(n)。
O(n^2)的方法：
#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#include <stack>using namespace std;stack<int> index;int a[15010], dp[15010], front[15010];//front记结点前驱int n;inline void ir() { cin >> n; return;}int main() { ir(); int maxn = 0; for (int i = 1; i <= n; i++) { scanf_s("%d", &a[i]); dp[i] = 1; front[i] = -1; //初始化 for (int j = 1; j < i; j++) if (a[j] < a[i]) { if (dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1;front[i] = j; } } maxn = max(maxn, dp[i]); } cout << maxn << endl; int k = 0; for (int i = 1; i <= n; i++) if (dp[i] == maxn) k = i; while (k != -1) { index.push(k); k = front[k]; } while (!index.empty()) { cout << a[index.top()] << endl; index.pop(); } return 0;}O(n log n)的方法：
#include <cstdio>#include <algorithm>using namespace std; int n,a[20010];int c[20010];int len=0; int find(int x){ int l=1,r=len,mid; while(l<=r) { mid=(l+r)>>1; if(x>c[mid])l=mid+1; //记忆方法:求上升序列，就表示x更大，那幺就是大于 else r=mid-1; } return l;} int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++) { int k=find(a[i]); c[k]=a[i]; len=max(len,k); } printf("%d",len); return 0;}套用
LIS经常用于确定一个代价最小的调整方案，使一个序列变为升序。只需要固定LIS中的元素，调整其他元素即可。