最長上升子序列LIS算法實現(xiàn)

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

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

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

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

　　下面是模板：

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

　　//入口參數(shù)：1.數(shù)組名稱 2.數(shù)組長度(注意從1號位置開始)

　　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月計算機等級考試成績查詢時間匯總

　　2011年計算機等級考試二級C++輔導筆記匯總

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

　　2011計算機等級考試二級C++輔導實例編程匯總