题目描述

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

样例

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

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

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

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

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

算法

(贪心) $O(nlgn)$

  for(int i = 0;i < n;i ++)
    {
        int l = 0;
        int r = len;
        while(l < r)
        {
            int mid = r+l+1>> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        q[r+1] = a[i];
        len = max(len,r+1);

    }
通过这段代码不断更新每个长度的最后一个数符合条件的最小的值
不懂可以听y总讲， 这里我说一个y总没讲，但是我没懂的问题：
就是这个方法不会保证顺序 即 最后一个数可以更新到第一位去但是没有关系
因为前面已经有数填过了，直接举例吧：
输入：3 1 2 1 8 5 6
我们一步一步走：

步骤  当前数 q数组变化   当前len   操作解释
初始  -   [-∞]    0   初始化哨兵
1   3   [-∞, 3] 1   3 > q[0]，插入q[1]，len更新为1
2   1   [-∞, 1] 1   1在q[1]的位置替换3（更小的末尾值，为未来可能更长的序列做准备）
3   2   [-∞,1, 2]   2   2 > q[1]=1，插入q[2]，len更新为2
4   1   [-∞,1,2]    2   这个1只能替换q[1]=1（相同值，无变化）
5   8   [-∞,1,2,8]  3   8 > q[2]=2，插入q[3]，len更新为3
6   5   [-∞,1,2,5]  3   5替换q[3]=8（更小的末尾值，为后续可能出现的6做铺垫）
7   6   [-∞,1,2,5,6]    4   6 > q[3]=5，插入q[4]，len更新为4
最终输出 len=4，对应的最长子序列是 1→2→5→6（注意这里虽然8被替换为5，但已记录的len=3不会被回退）

Q1：为什么覆盖前面的值不会破坏结果？
覆盖的是未来的可能性：当我们将 q[3]=8 覆盖为 q[3]=5 时，之前的len=3仍然有效（因为8已经贡献过长度3的计数了）。

历史长度被锁定：len 变量只记录历史最大值，后续操作只能增加它，不会减少。

Q2：如何处理顺序问题？
q数组不记录具体序列：它只记录不同长度的最小末尾值。比如在步骤2中，q[1]从3变成1，这相当于说：

之前存在长度为1的序列 [3]

现在发现更优的长度为1的序列 [1]（末尾更小，更容易让后续数字形成更长的序列）

真实的最长子序列可能被覆盖，但最长长度不会丢失：例如样例中 1→2→8 被 1→2→5→6 取代，但len会从3增长到4。

！！！！！！！ 也就是是说len只会在a[i]出现大于q[r]时才会更新

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 100000 + 20;

int a[N];
int q[N];

int n;

int main()
{
    cin>>n;
    for(int i = 0;i < n;i ++)
    {
        cin>>a[i];
    }
    int len = 0;
    q[0] = -2e9;
    for(int i = 0;i < n;i ++)
    {
        int l = 0;
        int r = len;
        while(l < r)
        {
            int mid = r+l+1>> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        q[r+1] = a[i];
        len = max(len,r+1);

    }
    cout<<len<<endl;
    return 0;
}