AcWing 896. 最长上升子序列 II 【贪心+二分】

末蓝、 2021-07-24 21:57 278阅读 0赞

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

### 目录 ###

*   *   *  1.题目
         *  2.思路 (贪心+二分) O(nlogn)
         *  3.代码

### 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;
    }