AcWing 896. 最长上升子序列 II（贪心）

题目链接

题目描述

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

题目模型

• 题目分析：

1. 对于下图所示样例，当某一个数能放在3后面时，肯定能放在1后面。所以我们只需记录每一个长度下最后一个元素的最小值是多少就可以了。
   
2. 用q[i]数组记录长度为i的上升子序列最后一个值是多少。
3. 对于每一个a[i]结尾的上升子序列，我们只需二分找到每种长度下小于a[i]的最大值，假设对应长度为4，此时q5≥a[i]，所以需要更新q5的值。
   

题目代码

#include 
#include 
#include 

using namespace std;

const int N = 100010;

int n;
int a[N], q[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    
    int len = 0;  //用len来记录长度的最大值
    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;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i]; 
    }
    
    printf("%d\n", len);
    
    return 0;
}