2011年計算機等級考試二級C++輔導(dǎo)實例編程(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):維護一個一維數(shù)組c，并且這個數(shù)組是動態(tài)擴展的，初始大小為1，c[i]表示最長上升子序列長度是i的所有子串中末尾最小的那個數(shù)，根據(jù)這個數(shù)字，我們可以比較知道，只要當前考察的這個數(shù)比c[i]大，那么當前這個數(shù)一定能通過c[i]構(gòu)成一個長度為i+1的上升子序列。當然我們希望在C數(shù)組中找一個盡量靠后的數(shù)字，這樣我們得到的上升子串的長度最長，查找的時候使用二分搜索，這樣時間復(fù)雜度便下降了。

　　模板如下：

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

　　//入口參數(shù):數(shù)組名+數(shù)組長度，類型不限，結(jié)構(gòu)體類型可以通過重載運算符實現(xiàn)

　　//數(shù)組下標從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++輔導(dǎo)筆記匯總

　　2011年上半年計算機等級考試報名時間匯總

　　2011計算機等級考試二級C++輔導(dǎo)實例編程匯總