C++ :

#include <bits/stdc++.h>
using namespace std;

/*
  10,9,2,5,3,7,101,18
  用dp数组来存储：生成的上升子序列 
  思路：
  第1个数10，最长LIS是10，长度是1
  第2个数是9<10，将10替换为9，LIS是9，长度还是1
  第3个数是2<9，将9替换为2，LIS是2，长度还是1
  第4个数是5>2，连接到LIS上，LIS是2 5，长度是2 
  第5个数是3<5，替换5位3，LIS是2 3，长度为2
  第6个数是7>3，连接到LIS上，LIS是2 3 7，长度为3
  第7个数是101>7，连接到LIS上，LIS是2 3 7 101，长度为4
  第8个数是18<101，替换101位18，LIS是2 3 7 18，长度为4 
*/

int a[100100];
int f[100100];
int main() {
	int n;
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	
	
	f[1]=a[1];
	int len=1;//通过记录f数组的有效位数，求得个数
	
	/*因为上文中所提到我们有可能要不断向前寻找，
	所以可以采用二分查找的策略，这便是将时间复杂
	度降成nlogn级别的关键因素。*/
	for(int i=2; i<=n; i++) {
		//如果刚好大于末尾，暂时向后顺次填充
		if(a[i] > f[len]) f[++len] = a[i];
		else {
			int l=1,r=len,mid;
			//二分找到数组中第1个比a[i]大的元素，替换掉这个元素 
			while(l < r) {
				mid=(l+r) / 2;
				if(a[i] <= f[mid]) r=mid;
				//如果仍然小于之前所记录的最小末尾，那么不断
				//向前寻找(因为是最长上升子序列，所以f数组必然满足单调)
				else l=mid+1;
			}
			
			//更新最小末尾
			f[l]=a[i];
		}
	}
	
	cout<<len;
}