2011年计算机二级C 辅导实例编程（27）

文章作者 100test 发表时间 2011:03:18 20:31:25
来源 100Test.Com百考试题网

　　最长上升子序列LIS算法实现

　　最长上升子序列问题是各类信息学竞赛中的常见题型，也常常用来做介绍动态规划算法的引例，笔者接下来将会对POJ上出现过的这类题目做一个总结，并介绍解决LIS问题的两个常用算法(n^2)和(nlogn).

　　问题描述:给出一个序列a1,a2,a3,a4,a5,a6,a7....an,求它的一个子序列(设为s1,s2,...sn)，使得这个子序列满足这样的性质，s1

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

　　算法1(n^2):我们依次遍历整个序列，每一次求出从第一个数到当前这个数的最长上升子序列，直至遍历到最后一个数字为止，然后再取dp数组里最大的那个即为整个序列的最长上升子序列。我们用dp[i]来存放序列1-i的最长上升子序列的长度，那么dp[i]=max(dp[j]) 1,(j∈[1, i-1]). 显然dp[1]=1,我们从i=2开始遍历后面的元素即可。

　　下面是模板：

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

　　//入口参数：1.数组名称 2.数组长度(注意从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