最长上升子序列 LIS nlogn

给出一个 1 ∼ n (n ≤ 10^5) 的排列 P 
求其最长上升子序列长度

Input

第一行一个正整数n，表示序列中整数个数； 
第二行是空格隔开的n个整数组成的序列。

Output

最长上升子序列的长度

 

题解

 

这里给出两种方法，先说经典版本的，设dp【i】表示以以 a【i】为结尾的LST的长度，n方的暴力很好想，显然我们在i之间找到一个最大的LST，且要保证a[j]<a[i]，那么显然dp[i]=max(dp[i],dp[j]+1)，那么这个dp显然就是在i之前找到一个以小于a[i]结尾元素，用来更新当前的a[i]，我们可以直接用满足条件的最长LST来更新就可以了……

所以就用棵线段树来维护一下1到a[i]-1的dp数组的最大值就可以了。代码讲完一起贴。

然后是鬼畜版本的，当然主要是状态，要绕下弯，设dp[i]表示长度为i的LST，结尾元素的最小值，为什么会想到这个，因为显然结尾的值越小，转移更优，然后显然dp数组是单调的，那么就好办了，我们每次枚举一个序列的元素，去更新，更新当前可以更新的最大的长度，更新的条件就是元素x>dp[i],然后二分出最大的i就可以，也只要更新最大的i就可以了为什么就自己想想吧，还比较有思考价值……

 

经典版：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
const int MAXN=100010;
using namespace std;
struct tree{
    int l,r,ma;
}a[4*MAXN];
int dp[MAXN],n,ans=0,nn=0;
int lian[MAXN]; 
 
void cl(){
    memset(dp,0,sizeof(dp));
    memset(lian,0,sizeof(lian));
}
 
void build(int id,int l,int r){
    if(l==r){
        a[id].l=l;
        a[id].r=r;
        a[id].ma=0;
        return; 
    }
    a[id].l=l;
    a[id].r=r;
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    a[id].ma=max(a[id*2].ma,a[id*2+1].ma);
}
 
int kanxun(int id,int l,int r){
    int L=a[id].l,R=a[id].r,mid=(L+R)/2;
    if(l==L&&r==R){
        return a[id].ma;
    }
    if(r<=mid) return kanxun(id*2,l,r);
    if(l>mid) return kanxun(id*2+1,l,r);
    else return max(kanxun(id*2,l,mid),kanxun(id*2+1,mid+1,r));
}
 
void insert(int id,int aum,int x){
    int l=a[id].l,r=a[id].r,mid=(l+r)/2;
    if(l==r&&l==aum){
        a[id].ma=x;
        return;
    }
    if(aum<=mid) insert(id*2,aum,x);
    else insert(id*2+1,aum,x);
    a[id].ma=max(a[id*2].ma,a[id*2+1].ma);
}
 
int main(){
    cl();
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&lian[i]),nn=max(nn,lian[i]);
    dp[0]=0;
    build(1,1,nn);
    for(int i=1;i<=n;i++){
        int j;
        if(lian[i]==1) j=0;
        else j=kanxun(1,1,lian[i]-1);
        dp[i]=j+1;
        insert(1,lian[i],dp[i]);
    }
    for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
    printf("%d",ans);
}  

鬼畜版：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
using namespace std;
int dp[1000010];
int main(){
    memset(dp,0,sizeof(dp));
    int n,maxi=0,l,r,mid,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        l=1,r=maxi,ans=0;
        while(l<=r){
            mid=(l+r)/2;
            if(x>=dp[mid]) ans=mid,l=mid+1;
            else r=mid-1;
        }
        if(ans==maxi) dp[++maxi]=x;
        else dp[ans+1]=min(dp[ans+1],x);
    }
    printf("%d",maxi);
    return 0;
}