题目描述

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

数据范围

1≤ N ≤100000，
−1e9 ≤ 数列中的数 ≤1e9

样例

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

blablabla

算法

(贪心 + 二分) $O(nlogn)$

因为数据范围比较大，采用动态规划的方式时间复杂度为$O(n ^ 2)$,会超时,故行不通。

要上子序列尽可能的长 那么久要求其上升的尽可能的慢， 显然当前最后一个元素越小，越有利于添加新的元素，这样LIS长度自然更长。

所以我们开辟一个数组来保存上升子序列，在遍历数组的过程中维护它

• 如果数组的当前数大于上升子序列的最后一个数，那么将其直接接到上升子序列的后面
• 否则，替换上升子序列中大于等于当前数的最小的数，也就是第一个大于等于当前数
  • 因为上升子序列有序，所以用二分来查找

复杂度

时间复杂度： 遍历数组 + 二分查找 $O(nlogn)$
空间复杂度： 用来保存上升子序列,最长为原数组的长度n $O(n)$

C++ 代码

// n^2 会超时  
// 最长上升子序列情况是  1000 不会超时

#include <iostream>
#include <algorithm>

using namespace std;

const int N  = 100010;

int n;
int a[N];
int q[N];  // 保存上升子序列  

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) 
        scanf("%d", &a[i]);

    // 上升子序列初始化  len为其长度    
    q[0] = a[0];
    int len = 1;

    // 从第二个数开始遍历
    for(int i = 1; i < n; i++)
    {   
        // 如果a[i]比q[]的最后一个大,那么将a[i] 直接接在后面
        if(q[len - 1] < a[i])
        {
            len ++;
            q[len - 1] = a[i];
            continue;
        }
        // 否则 a[i] 应该替换 第一个大于等于其本身的数
        int l = 0, r = len - 1;
        while(l < r)  
        {
            int mid = l + r >> 1;
            if(q[mid] >= a[i]) r = mid;
            else l = mid + 1;
        }
        q[l] = a[i];  // 将其替换掉
    }

    printf("%d\n", len);

    return 0;
}