最長上升子序列(LIS)的O(nlogn) & O(n^2)算法 - 動态規劃

問題描述

給你一個數列，請你找出該序列數字依次遞增的子序列(注意子序列不要求數字相鄰)。例如1、7、3、5、9、4、8。其中一次遞增的子序列有(1、7)，(1、3、5、9)，(1、3、4、8)等，其中最長的長度為4。

輸入描述

輸入包含多組資料，每組資料第一行包含一個正整數n（1≤n≤1000）。

緊接着第二行包含n個正整數m（1≤n≤10000）。

輸出描述

對應每一組資料，輸出最長遞增子序列的長度。

輸入

7

1 7 3 5 9 4 8

6

1 3 5 2 4 6

輸出

4

4

題解

O(n^2)算法

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int a[],dp[];
int n;
int LIS()
{
    int i,j,ans,m;
    dp[]=;
    ans=;
    for(i=;i<=n;i++){
        m=;
        for(j=;j<i;j++){
            if(dp[j]>m&&a[j]<a[i])
                m=dp[j];
        }
        dp[i]=m+;
        if(dp[i]>ans)
            ans=dp[i];
    }
    return ans;
}
int main()
{
    while(~scanf("%d",&n)){
        for(int i=;i<=n;i++){
            scanf("%d",&a[i]);
        }
        printf("%d\n",LIS());
    }
    return ;
}
           

O(nlogn)算法

隻管維持一個最小的遞增子序列即可。

#include <cstdio>
#include <iostream>
using namespace std;

int a[],dp[];
int n;
int main()
{
    while(~scanf("%d",&n)){
        for(int i=;i<=n;i++){
            scanf("%d",&a[i]);
        }
        dp[]=a[];
        int len=;
        for(int i=;i<=n;++i){
            if(a[i]>dp[len])
                dp[++len]=a[i];
            else{
                int pos=lower_bound(dp,dp+len,a[i])-dp;
                dp[pos]=a[i];
            }
        }
        printf("%d\n",len);
    }
    return ;
}