利用了二分的思想来找已经放进去的第一个比读入元素大的位置，然后替换一下就行，如果读入的数比头上的数目还大，那么更新头部，加入一个新的数，最后这个数组的大小就是最长的上升子序列了，复杂度大约nlogn，比传统的n2快了不少；
/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
int a[100001]; //记录数组
int main()
{
#ifdef LOCALfreopen("ride.in","r",stdin);freopen("ride.out","w",stdout);
#endifint n, m, cnt, high, low, mid, i;while(scanf("%d", &n) != EOF){cnt = 0; //最长序列个数for(i = 1; i <= n; i++){scanf("%d", &m);if(cnt == 0 || m > a[cnt]) //如果是第一个或者比队头的大，则存入数组a[++cnt] = m;else{high = cnt;low = 1;while(low <= high) //在已存序列中寻找位置，将输入的数替换进去，这样可以保证一直是上升序列{mid = (low + high) / 2;if(a[mid] < m)low = mid + 1;else high = mid - 1;}a[low] = m;}}printf("%d\n", cnt);}return 0;
}