当前位置: 首页 > news >正文

郑州做网站便宜晋城建设路网站

郑州做网站便宜,晋城建设路网站,网站建设 计划书,建筑设计用什么软件单调子序列包含有单调递增子序列和递减子序列#xff0c;不失一般性#xff0c;这里只讨论单调递增子序列。首先#xff0c;从定义上明确我们的问题。给定序列a1, a2, …, an#xff0c;如果存在满足下列条件的子序列 ai1ai2…aim, (其中i1i2…im)…单调子序列包含有单调递增子序列和递减子序列不失一般性这里只讨论单调递增子序列。首先从定义上明确我们的问题。给定序列a1, a2, …, an如果存在满足下列条件的子序列 ai1ai2…aim, (其中i1i2…im) 即称为一个原序列的长度为m的单调递增子序列那么现在的问题是我们要找出一个序列的最长的单调递增子序列。     直观上来说一个序列Sn它有2n个子序列枚举所有的子序列找出其中单调递增的序列然后返回其中最长的这样我们的问题就解决了。当然这个直观的算法在时间上为O(2n*n)它的复杂度增长太快了所以我们还应该做得更好一些。     于是我们换个角度思考。假设我们对Sn排序递增得到Sn’。那么Sn和Sn’的最长公共子序列Cm就是我们要求的最长单调递增子序列如果你不清楚最长公共子序列的定义just google it。为什么假设Cm’是Sn的最长单调子列且Cm’!Cm Cm’的长度大于Cm。由于Cm’是递增的并且Cm’的每一个元素都来自Sn所以Cm’一定是Sn’的子列而Cm’又是Sn的子列所以Cm’是Sn和Sn’的公共子列故Cm’的长度一定小于Cm这与假设矛盾所以Cm是最长单调子列。理论上我们的算法是正确的复杂度方面运用动态规划(dynamic programming)来求解LCS最长公共子列Longest-Common-Subsequence时间上是O(n2)空间上也是O(n2)。于是对Sn排序需要nlogn的时间而LCS需要n2最后我们的算法时间上是O(n2)。     可以看到通过上面的改进我们的算法效率得到了很大的提升从指数增长到多项式增长。不过程序设计的乐趣就是它会不断地给我们一些惊喜所以就此打住不是我们该做的于是更好的算法应该是存在的。     对于序列Sn考虑其长度为i的单调子列(1im)这样的子列可能有多个。我们选取这些子列的结尾元素子列的最后一个元素的最小值。用Li表示。易知 L1L2…Lm 如果LiLj(ij)那么去掉以Lj结尾的递增子序列的最后j-i个元素得到一个长度为i的子序列该序列的结尾元素akLjLi这与Li标识了长度为i的递增子序列的最小结尾元素相矛盾于是证明了上述结论。现在我们来寻找Sn对应的L序列如果我们找到的最大的Li是Lm那么m就是最大单调子列的长度。下面的方法可以用来维护L。     从左至右扫描Sn对于每一个ai它可能 (1)    aiL1那么L1ai (2)    aiLm那么Lm1aimm1 (其中m是当前见到的最大的L下标) (3)    LsaiLs1那么Ls1ai     扫描完成后我们也就得到了最长递增子序列的长度。从上述方法可知对于每一个元素我们需要对L进行查找操作由于L有序所以这个操作为logn于是总的复杂度为O(nlogn)。优于开始O(n2)的算法。这里给出我的一个实现算法并没有返回具体的序列只是返回长度    1 template typename T 2 int LMS (const T * data, int size) 3 ...{ 4 if (size 0) 5 return 0; 6 7 T * S new T[size]; 8 int S_Count 1; 9 S[0] data[0];10 11 for (int i 1; i size; i)12 ...{13 const T e data[i];14 int low 0, high S_Count - 1;15 16 while (low high)17 ...{18 int mid (low high) / 2;19 20 if (S[mid] e)21 break;22 else if (S[mid] e)23 ...{24 high mid - 1;25 }26 else27 ...{28 low mid 1;29 }30 }31 32 //well, in this point33 //high is -1, indicating e is the smallest element.34 //otherwise, high indicates index of the largest element that is smaller than e35 if (high S_Count - 1)36 S[S_Count] e;37 else38 S[high 1] e;39 }40 41 return S_Count;42 } 转载于:https://www.cnblogs.com/ITXIAZAI/p/4111294.html
http://www.sadfv.cn/news/227865/

相关文章:

  • 青岛seo网站排名外包加工网合法吗
  • 私活做网站网站焦点图怎么做
  • 个人网站开发工具备案需要写网站建设方案书
  • 个人做电影网站合法吗反向代理
  • 网站建设公司自贡php企业网站开发框架
  • 做网站提升公司形象离石做网站的公司
  • 邢台网络优化技术公司深圳seo推广
  • 佛山网站建设的大品牌网站主要盈利模式
  • 帮做网站设计与规划作业上海网站
  • 贸易网站模板滴滴出行的网站是哪家公司做的
  • 个人资质网站做推广设计一个个人求职网站
  • 做石油期货看什么网站公共营养师报考条件
  • 方城网站制作wordpress手机字体变大6
  • 一站式网站建设设计jquery timelinr wordpress
  • 沈阳网站建设三好街推广产品引流的最佳方法
  • 数据做图网站wordpress 跳转适配
  • 做网站这么便宜可以吗菜馆网站制作
  • 杭州网站定制开发广东省建设厅投诉网站首页
  • 网站关键字优化地点wordpress滑动解锁
  • 学院网站设计方案谷德建筑设计网
  • 电子商务概论考试题及答案seo服务商
  • 全国医院网站建设小网站怎么建设
  • 团购网站自个做做公益网站需要什么资质
  • 网站做镜像检查漏洞网站开发 原理
  • 南阳提高网站排名w5500做服务器网站
  • 百度seo 站长工具湛江找人做网站排名
  • 荆州网站建设广州公司网站建设公司
  • 海南住建部建设网站的网站咨询行业网站制作
  • 做摄像头模组的网站用国外服务器做违法网站
  • 手机wap网站程序南京网站设计费用