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

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
   
    #include
    
     #include
     
      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
      
       >1;            if(q[mid]