问题

经典的LIS(Longest Increasing Sequence)问题，即求序列的最长严格递增子序列的长度。

思路

解决这道题的思路的核心在于对每个元素，看这个元素是否能接到前面的某个上升子序列上，从而扩展上升子序列的长度。

而 前面的上升子序列 有很多，我们需要怎么分类呢？根据分类方式的不同，有两种算法：
1. 按照末尾元素的值分类，这是最直观的，把前面每个元素都看作一个上升子序列的末尾元素，对应算法1（DP）
2. 按照上升子序列的长度分类，为什么呢？因为按照第一种分类方式可能有冗余：某些元素的值很大又很靠前，后面不太可能有元素能接到它的后面。所以我们用更严格的分类方式：按照上升子序列的长度分类，每一类只存末尾最小的元素，使得最大化后继接上的元素。该分类方式对应算法2（贪心 + 二分）

算法1：线性dp $O(N^2)$ TLE

对于每个当前元素，检查前面的所有元素，看是否能接到某些元素后面，并更新最长上升子序列。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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


int main(){
    cin>>n;
    int res = 1;
    for(int i = 1; i <= n; i ++){
        cin>>a[i];
    }
    for(int i = 1; i <= n; i ++){
        f[i] = 1;
        for(int j = 1; j < i; j++){
            if(a[j] < a[i]){
                f[i] = max(f[i],f[j]+1);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        res = max(res, f[i]);
    }   
    cout<<res;
}

算法2：贪心+二分 $O(NlogN)$

按照上升子序列的长度分类，每个长度只存储最小的末尾元素值，即f[i]: 长度为i的上升子序列最小末尾元素值

不断更新最长长度和每个上升子序列的最小末尾元素值。

由于长度越长，末尾元素值越大（长度为k的上升子序列末尾元素值一定比长度为k-1的末尾元素值大，因为长度为k的上升子序列倒数第二个元素严格小于末尾元素）

所以f是递增的，可以用二分将当前数接在最大的小于它的数后面

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N]; // q[i]: 长度为i的上升子序列最小末尾元素值

int main()
{
    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;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }

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

    return 0;
}