最长不上升子序列

luckydrawbox · 2021-08-30 00:02:24 · 个人记录

LIS(n,a)：求 a_{1\sim n} 中的最长不上升子序列的长度。

int LIS(int n,int *a){
    int dp[N],l=1,p;
    dp[1]=a[1];
    for(int i=2;i<=n;i++)
        if(dp[l]>=a[i])
            dp[++l]=a[i];
        else
            dp[upper_bound(dp+1,dp+1+l,a[i],greater<int>())-dp]=a[i];
    return l;
}

空间复杂度 O(n)，时间复杂度 O(n\log n)。