思路：

dp[i]记录长为i的子序列的最小结尾值。
1. 对于每一位的数，如果该数比dp[]数组末尾的数还大，它可以让dp[]数组长度加1。把它追加在数组尾部。
2. 如果它不能让dp[]数组长度增加，查看它是否能更新某个结尾值（因为子序列结尾值越小，意味着后面可能加进来的就越多）。
最终结果是dp数组的长度。
时间复杂度为O(nlogn)

举个例子：

                    3 1 2 1 8 5 6

look at 3 -> dp[1]: 3
look at 1 -> dp[1]: 1
look at 2 -> dp[2]: 1 2
look at 1 -> dp[2]: 1 2
look at 8 -> dp[3]: 1 2 8
look at 5 -> dp[3]: 1 2 5
look at 6 -> dp[4]: 1 2 5 6

final result: len(maximum increasing subsequence) = len(dp) = 4

偷懒法：使用lower_bound函数

int lower_bound(arr[], arr[] + size, item)返回第1个>=item的数组元素的地址
想用作下标需要用地址减去数组首地址

#include<iostream>
using namespace std;

const int N = 100010;

int n, cnt;
int a[N], dp[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    dp[1] = a[1]; cnt = 1;
    for(int i = 2; i <= n; i++){
        if(a[i] > dp[cnt]) //如果当前数比dp数组结尾大，则直接加到结尾
            dp[++cnt] = a[i];
        else{
            int ptr = lower_bound(dp + 1, dp + cnt + 1, a[i]) - dp;
            dp[ptr] = a[i];
        }
    }
    cout << cnt << endl;
}

手写二分法

因为是要找到>=a[i]的第一个元素，所以是找右半段段首，故使用y总二分板子中的第一种，if xx >= a[i] r = mid

#include<iostream>
using namespace std;

const int N = 100010;

int n, cnt;
int a[N], dp[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    dp[1] = a[1]; cnt = 1;
    for(int i = 2; i <= n; i++){
        if(a[i] > dp[cnt]) //如果当前数比dp数组结尾大，则直接加到结尾
            dp[++cnt] = a[i];
        else{
            int l = 1, r = cnt, mid;
            while(l < r){ 
                mid = (l + r) / 2;
                if(dp[mid] >= a[i]) r = mid;
                else  l = mid + 1;
            }
            dp[l] = a[i];
        }
    }
    cout << cnt << endl;
}