思路

首先需要用到一个数组 $low$ ，$low[i]=$ 长度为 $i$ 的上升子序列末尾一个数的最小值。为什么是最小值呢？通过贪心的思想来说，序列最后一位越小后面能加上的元素就越多。随后，遍历一个元素数组 $a$ ，对于 $a[i]$ ，如果它大于 $low[ans]$ ( $ans$ 是当前的最长的子序列长度)，则插到子序列的后面，即 $ans$ 加一，$low[ans]$ 赋值为 $a[i]$ （此时 $ans$ 的值已经自增）。否则，就用 $a[i]$ 维护 $low$ 数组：把 $a[i]$ 替换掉当前子序列中小于 $a[i]$ 的最大的一项。

代码

#include<bits/stdc++.h>
using namespace std;
int low[max_n],a[max_n];
int ans;
int bi_search(int* address, int r, int border){
    int l = 0;
    while(l<r){
        int mid = (l+r)/2;
        if(address+mid > boder){
            r = mid -1;
        }else{
            l = mid +1;
        }
    }
    return l;
}
int main(){
    for(int i= 0; i < n; i++){
        cin >> a[i];
        low[i] = 0x3f3f3f3f;//无穷大
    }
    low[1] = a[0];
    ans = 1;//a[0]单独组成序列
    for(int i = 0; i < n; i++){
        if(a[i] > low[ans]){
            low[++ans] = a[i];
        }else{
            low[bi_search(low,ans,a[i])] = a[i];
        }
    }
    cout << ans;
    return 0;
}