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

　　模板如下：

　　//最長(zhǎng)上升子序列nlogn模板

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

　　//數(shù)組下標(biāo)從1號(hào)開始。

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

　　template

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

　　{

　　int l=1, r=n;

　　while(l<=r)

　　2010年9月計(jì)算機(jī)等級(jí)考試成績(jī)查詢時(shí)間匯總

　　2011年計(jì)算機(jī)等級(jí)考試二級(jí)C++輔導(dǎo)筆記匯總

　　2011年上半年計(jì)算機(jī)等級(jí)考試報(bào)名時(shí)間匯總

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