思路

长度1000允许二次DP；标程用尾数组二分，作优化路线关联，区分严格上升与非降。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){int n,x;cin>>n;vector<int>t;while(n--){cin>>x;auto p=lower_bound(t.begin(),t.end(),x);if(p==t.end())t.push_back(x);else *p=x;}cout<<t.size()<<'\n';}