#include
    
     #include
     
      int len, n, i, j; int d[100005], a[100005]; int binsearch(int x) { 	int l = 1, r = len, mid;	while (l <= r)	{    		mid = (l + r) >> 1;		if (d[mid-1] <= x && x < d[mid]) return mid;		else if (x > d[mid]) l = mid + 1;		else r = mid - 1;     	}  }int main(){	while(scanf ("%d", &n)!=EOF)		{		for (i = 1; i<= n; i++)		scanf ("%d", &a[i]);		memset (d, 0, sizeof (d));		d[1] = a[1];		len = 1;		for (i = 2; i <= n; i++)		{   			if (a[i] < d[1]) j = 1;			else if (a[i] > d[len]) j = ++len;			else j = binsearch (a[i]);			d[j] = a[i];   		}		printf ("%d\n", len);  	}return 0;}
     
    

以上是AC的代码，来源于：http://qiemengdao.iteye.com/blog/1660229

很好的一篇文章，可以解释公共子序列的很多问题