LIS(最長上升子序列（計算機科學）)

最長上升子序列（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中的元素，調整其他元素即可。