最長(zhǎng)上升子序列LIS算法實(shí)現(xiàn)

　　最長(zhǎng)上升子序列問(wèn)題是各類信息學(xué)競(jìng)賽中的常見(jiàn)題型，也常常用來(lái)做介紹動(dòng)態(tài)規(guī)劃算法的引例，筆者接下來(lái)將會(huì)對(duì)POJ上出現(xiàn)過(guò)的這類題目做一個(gè)總結(jié)，并介紹解決LIS問(wèn)題的兩個(gè)常用算法(n^2)和(nlogn).

　　問(wèn)題描述:給出一個(gè)序列a1,a2,a3,a4,a5,a6,a7....an,求它的一個(gè)子序列(設(shè)為s1,s2,...sn)，使得這個(gè)子序列滿足這樣的性質(zhì)，s1

　　例如有一個(gè)序列:1 7 3 5 9 4 8,它的最長(zhǎng)上升子序列就是 1 3 4 8 長(zhǎng)度為4.

　　算法1(n^2):我們依次遍歷整個(gè)序列，每一次求出從第一個(gè)數(shù)到當(dāng)前這個(gè)數(shù)的最長(zhǎng)上升子序列，直至遍歷到最后一個(gè)數(shù)字為止，然后再取dp數(shù)組里最大的那個(gè)即為整個(gè)序列的最長(zhǎng)上升子序列。我們用dp[i]來(lái)存放序列1-i的最長(zhǎng)上升子序列的長(zhǎng)度，那么dp[i]=max(dp[j])+1,(j∈[1, i-1]); 顯然dp[1]=1,我們從i=2開(kāi)始遍歷后面的元素即可。

　　下面是模板：

　　//最長(zhǎng)上升子序列(n^2)模板

　　//入口參數(shù)：1.數(shù)組名稱 2.數(shù)組長(zhǎng)度(注意從1號(hào)位置開(kāi)始)

　　template

　　int LIS(T a[],int n)

　　{

　　int i,j;

　　int ans=1;

　　int m=0;

　　int *dp=new int[n+1];

　　dp[1]=1;

　　for(i=2;i<=n;i++)

　　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í)例編程匯總