题目描述

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

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

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

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

数据范围
1≤N≤100000，
−109≤数列中的数≤109

样例

输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
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 ){

            int mid = l + r + 1 >> 1;

            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        /**
         * 当r = len时，代表从q[0] ~ q[len]中小于a[i]的最大值就是数组q的最后一个数q[len];此时q数组的长度应该加1，并且q[len+1]=a[i]
         * 
         * 当r < len时，代表从q[0] ~ q[len]中找到了一个q[k]<a[i],且k < len;此时q数组的长度不变，可以直接令q[k+1]=a[i],因为此时q[k+1]>a[i]
         * */

        len = max ( len, r+1 );
        q[r+1] = a[i];
    }


    printf("%d",len);
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla