设为首页 加入收藏

TOP

2011年计算机二级C++辅导实例编程(27)
2014-10-19 00:09:11 】 浏览:1571
Tags:2011年 计算机 二级 辅导 实例 编程

  最长上升子序列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<=n;i++)


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇2011年计算机二级C++辅导实例编程.. 下一篇2011年计算机二级C++辅导实例编程..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目