对于那个O(nlgn)的算法实在用的不熟,大概能理解,不过还是欠火候,在此不贴了,以后再重新编辑

 

#include
    
     #include
     
      #include
      
       #include
       
        int LIS(int *a, int n){	assert(NULL != a);	int *dp = new int[n];	memset(dp, 0, sizeof(dp));	for(int i=0; i
        
          a[j] && (dp[j]+1>dp[i]))				dp[i] = dp[j] + 1;		}	}	int ret = dp[n-1];	delete []dp;	return ret;}void test(){	int n = 0;	while(scanf("%d", &n)!=EOF)	{		if(n == 0) break;		int *a = new int[n];		for(int i=0; i