2011年计算机等级考试二级C++辅导实例编程(27)

　　{

　　m=0;

　　for(j=1;j

　　{

　　if(dp[j]>m&&a[j]

　　m=dp[j];

　　}

　　dp[i]=m+1;

　　if(dp[i]>ans)

　　ans=dp[i];

　　}

　　return ans;

　　}

　　算法2(nlogn):维护一个一维数组c，并且这个数组是动态扩展的，初始大小为1，c[i]表示最长上升子序列长度是i的所有子串中末尾最小的那个数，根据这个数字，我们可以比较知道，只要当前考察的这个数比c[i]大，那么当前这个数一定能通过c[i]构成一个长度为i+1的上升子序列。当然我们希望在C数组中找一个尽量靠后的数字，这样我们得到的上升子串的长度最长，查找的时候使用二分搜索，这样时间复杂度便下降了。

　　模板如下：

　　//最长上升子序列nlogn模板

　　//入口参数:数组名+数组长度，类型不限，结构体类型可以通过重载运算符实现

　　//数组下标从1号开始。

　　/**//////////////////////////BEGIN_TEMPLATE_BY_ABILITYTAO_ACM////////////////////////////

　　template

　　int bsearch(T c[],int n,T a)

　　{

　　int l=1, r=n;

　　while(l<=r)

　　2010年9月计算机等级考试成绩查询时间汇总

　　2011年计算机等级考试二级C++辅导笔记汇总

　　2011年上半年计算机等级考试报名时间汇总

　　2011计算机等级考试二级C++辅导实例编程汇总