最长上升子序列LIS模板

///最长上升子序列LIS模板
int BinSerch(int l,int r,int cut)
{
    while (l<=r)
    {
        int m=(l+r)>>1;
        if (cut>d[m]&&cut<=d[m+1]) return m;
        if (cut>d[m]) l=m+1;
        else r=m-1;
    }
    return 0;
}

int LIS(int n)
{
    int len=1,j;
    d[1]=a[0];
    for (int i=1;i<n;i++)
    {
        if (a[i]>d[len]) j=++len;
        else j=BinSerch(1,len,a[i])+1;
        d[j]=a[i];
    }
    return len;
}