二分

lower_bound

lower_bound()在一个区间内进行二分查找，返回第一个大于等于目标值的位置（地址）

upper_bound

upper_bound()与lower_bound()的主要区别在于前者返回第一个大于目标值的位置

int lowerBound(int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if (x>g[mid]) l=mid+1;
        else r=mid-1;
    }
    return l;
}
int upperBound(int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if (x>=g[mid]) l=mid+1;
        else r=mid-1;
    }
    return l;
}

最长上升子序列LIS

定义dp[i]为以i结尾的最长上升子序列长度，则dp[i]=max{0,d[j] | j<i && s[i]<s[j]}+1

最长上升子序列（>）相当于反序列的最长不上升子序列(<=)

int s[maxn],n;
int dp[maxn],g[maxn];
int main()
{
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++) scanf("%d",s+i);
        mem(g,0x3f);
        mem(dp,0);
        for(int i=0;i<n;i++){
            int k=lower_bound(g+1,g+n+1,s[i])-g;
            //int k=lowerBound(s[i]);
            dp[i]=k;
            g[k]=s[i];
        }
        int ans=-1;
        for(int i=0;i<n;i++) ans=max(ans,dp[i]);
        printf("%d\n",ans);
    }
    return 0;
}

================待更新==========

参考博客1：https://blog.csdn.net/Martin20150405/article/details/51930912

参考博客2：https://blog.csdn.net/wbin233/article/details/77570070

版权声明：本文为KeepZ原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/KeepZ/p/11285936.html