最长上升子序列

维护一个数组记录长度为i的上升子序列最后一个值
遍历原数组 二分查找该数组中小于等于的值 更新该值与答案
复杂度nlogn
leetcode300

int g[10009];
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    int len = 0;
    for(int i = 0; i < n; i ++)
        g[i] = 0x3fffffff;
    g[0] = -0x3fffffff;
    for(int i = 0 ; i < n ; i ++){
        int pos = lower_bound(g,g + len + 1,nums[i]) - g;
        g[pos] = min(g[pos],nums[i]);
        len = max(len,pos);    
    }
    return len;
}

最长公共子序列

将一个数组用另一个离散化，然后转化为最长上升子序列
luogu1439

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
const int maxn=100009;
int n,a[maxn],b[maxn],w[maxn],p[maxn],ans=1;
bool cmp(int A,int B){
    return w[A]<w[B]||(w[A]==w[B]&&A<B);
}
int main(){
    std::ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        cin>>b[i];
        w[b[i]]=i;
    }
    for(int i=1;i<=n;i++) a[i]=w[a[i]];
    for(int i=1;i<=n;i++) p[i]=0x7fffffff;
    for(int i=1;i<=n;i++){
        int x=lower_bound(p,p+ans+1,a[i])-p;
        //cout<<p[x]<<endl;
        p[x]=min(p[x],a[i]);
        if(x>ans) ans=x;
    }
    //for(int i=1;i<n;i++) cout<<p[i]<<' ';cout<<endl;
    cout<<ans<<endl;
    return 0;
}