题解 | #牛牛的装球游戏#

首先想好算法，一看最长上升子序列，那么比较脑子里应该出现几个dp式子： 接下来一看要求：空间复杂度 O (n) ，时间复杂度 O (n) 好家伙必须要on的复杂度 那么可以尝试结合其他算法去优化一个比较直接的dp，那么咱们首选二分！

二分的思路如下：

1. 先定义边界，l = 0, r = len, 其中len是q数组的长度
2. 然后确定check函数, 可以先找到不等式中c < x ≤ a ≤ b的c 通过q[r + 1] = a[i]来将x覆盖a的值 同时也要考虑算法1的情况1, 需要扩大q数组的长度
3. 即r + 1 > len时, 表示超出了二分边界，这时就要len ++更新q的长度
4. 时间复杂度
5. 遍历每个数是 O(n)
6. 遍历q数组每个数, 找到一个最大的小于当前数x的数O(logn)
7. 因此时间复杂度是 O(nlogn) C++ 代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 5;

int a[maxn], f[maxn];
int cnt;

inline int find(int x) {
    int l = 1, r = cnt; 
    while(l < r) {
        int mid = l + r >> 1;
        if(f[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return l;
}

int main(void) {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    f[++cnt] = a[1];
    for(int i = 2; i <= n; i ++) 
        if(a[i] > f[cnt]) f[ ++ cnt] = a[i];
        else {
            int tmp = find(a[i]);
            f[tmp] = a[i]; 
        }

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

    return 0;
}