本文共 1143 字，大约阅读时间需要 3 分钟。

hello大家好，欢迎大家访问 林深时不见鹿 的博客，算法小白，记录学习的点滴日常，致力于通俗易懂的题解，相遇即是上上签，如有不足，还请多多指教。

1.题目

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数N。

第二行包含N个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤100000，
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

2.思路 (贪心+二分) O(nlogn)

朴素版的LIS时间复杂度为O(n^2)会超时，因此这道题我们用贪心+二分来做。
先讲贪心思路:
我们定义一个数组q[],让q数组来存贮同一长度下的上升子序列结尾的最小值。因为如果我们可以接到一个更大的数后面，那么我们一定可以接到一个更小的数后面， 接到更小的数后面可以为我们留出更大的空间来接其他的数，使得数组的长度更长。可以证明q数组一定是单调上升的 最后q数组的长度就是答案 。
再讲二分:
如何更新q数组呢？
我们遍历原来的a数组，对于每个a[i],我们在q[]数组查找小于a[i]的最大的数x。找到以后我们将x的后一个数更新成a[i],因为x是小于a[i]的最大的数,那么x的后一个数一定是大于等于a[i]的。这个也好证明,如果x的后一个数也小于a[i],那么q数组中小于a[i]的的最大的数就不是x了而是x的后一个数了(数组q单调上升),这与我们二分的结果相反。

3.代码

#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int N=1e5+10;int a[N];int q[N];int main(){       int n;    scanf("%d",&n);    for(int i=0;i<n;i++) scanf("%d",&a[i]);    int len=0;    for(int i=0;i<n;i++)    {           int l=0,r=len;           while(l<r)  //二分去更新数组q        {               int mid=l+r+1>>1;            if(q[mid]<a[i]) l=mid;             else r=mid-1;        }         q[r+1]=a[i];         len=max(len,r+1);    }    printf("%d\n",len);     return 0;}