



免费预览已结束,剩余1页可下载查看
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
求数组中最长递增子序列写一个时间复杂度尽可能低的程序,求一个一维数组(N个元素)中的最长递增子序列的长度。例如:在序列1,-1,2,-3,4,-5,6,-7中,其最长的递增子序列为1,2,4,6。分析与解法根据题目的要求,求一维数组中的最长递增子序列,也就是找一个标号的序列b0,b1,bm(0 = b0 b1 bm N),使得arrayb0arrayb1arraybm。 解法一根据无后效性的定义我们知道,将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态来说,它以前各阶段的状态无法直接影响它未来的决策,而只能间接地通过当前的这个状态来影响。换句话说,每个状态都是历史的一个完整总结。同样的,仍以序列1,-1,2,-3,4,-5,6,-7为例,我们在找到4之后,并不关心4之前的两个值具体是怎样,因为它对找到6没有直接影响。因此,这个问题满足无后效性,可以通过使用动态规划来解决。可以通过数字的规律来分析目标串:1,-1,2,-3,4,-5,6,-7。使用i来表示当前遍历的位置当i=1时,显然,最长的递增序列为(1),序列长度为1.当i=2是,由于-11,2-1。因此,最长的递增序列为(1,2),(-1,2),长度为2。在这里,2前面是1还是-1对求出后面的递增序列没有直接影响。(但是在其它情况下可能有影响)依此类推之后,我们得出如下的结论。假设在目标数组array的前i个元素中,最长递增子序列的长度为LISi。那么,LISi+1=max1,LISk+1,arrayi+1arrayk,for any k = i即如果arrayi+1大于arrayk,那么第i+1个元素可以接在LISk长的子序列后面构成一个更长的子序列。于此同时arrayi+1本身至少可以构成一个长度为1的子序列。根据上面的分析,就可以得到代码清单C+代码:int Max(int *a, int n) int max = a0; for(int i = 1; i n; i+) if(max ai)max = ai; return max;int LIS(vector &array)int *a = new intarray.size();for(int i = 0; i array.size(); i+)ai = 1; /初始化默认的长度for(int j = 0; j array j & aj + 1 ai)ai = aj + 1;return Max(a, array.size();这种方法的时间复杂度为O(N2 + N) = O(N2) 解法二在前面的分析中,当考察第i+1个元素的时候,我们是不考虑前面i个元素的分布情况的。现在我们从另一个角度分析,即当考察第i+1个元素的时候考虑前面i个元素的情况。对于前面i个元素的任何一个递增子序列,如果这个子序列的最大的元素比arrayi+1小,那么就可以将arrayi+1加在这个子序列后面,构成一个新的递增子序列。比如当i=4的时候,目标序列为1,-1,2,-3,4,-5,6,-7最长递增序列为(1,2),(-1,2)。那么,只要42,就可以把4直接增加到前面的子序列中形成一个新的递增子序列。因此,我们希望找到前i个元素中的一个递增子序列,使得这个递增子序列的最大的元素比arrayi+1小,且长度尽量地长。这样将arrayi+1加在该递增子序列后,便可以找到以arrayi+1为最大元素的最长递增子序列。仍然假设在数组的前i个元素中,以arrayi为最大元素的最长递增子序列的长度为LISi。同时,假设:长度为1的递增子序列最大元素的最小值为MaxV1;长度为2的递增子序列最大元素的最小值为MaxV2;长度为LISi的递增子序列最大元素的最小值为MaxVLISi; 本循环不变式P是:P:k是序列a0:i的最长递增子序列的长度,0in。容易看出,在由i-1到i的循环中,ai的值起关键作用。如果ai能扩展序列a0;i-1的最长递增子序列的长度,则k=k+1,否则k不变。设a0;i-1中长度为k的最长递增子序列的结尾元素是aj(0ji-1),则当aiaj时可以扩展,否则不能扩展。如果序列a0;i-1中有多个长度为k的最长递增子序列,那么需要存储哪些信息?容易看出,只要存储序列a0;i-1中所有长度为k的递增子序列中结尾元素的最小值bk。因此,需要将循环不变式P增强为:P:0in;k是序列a0;i的最长递增子序列的长度;bk是序列a0;i中所有长度为k的递增子序列中最小结尾元素值。相应地,归纳假设也增强为:已知计算序列a0;i-1(in)的最长递增子序列的长度k以及序列a0;i中所有长度为k的递增子序列中的最小结尾元素值bk的正确算法。增强归纳假设后,在由i-1到i的循环中,当aibk时,k=k+1,bk=ai,否则k值不变。注意到当aibk时,k值增加,bk的值为ai。那么,当aibk时,bl;k的值应该如何改变?如果aibl,则显然应该将bl的只改变为ai,当blaibk时,注意到数组b是有序的,可以用二分搜索算法找到下标j,使得bj-1aibj。此时,b1;j-1和bj+1;k的值不变,bj的值改变为ai。/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */template vector find_lis(vector &a)vector b, p(a.size();/b是存储递增序列长度为k的最后元素下标 /比如b1是存储递增子序列最大元素的最小值的下标/b是存储最长子序列的下标 int u, v; if (a.size() 1)return b; b.push_back(0); for (int i = 1; i (int)a.size(); i+) if (ab.back() ai) pi = b.back(); b.push_back(i); continue; for (u = 0, v = b.size()-1; u v;) /二分搜索 int c =
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年Z世代消费行为对新兴品牌成长路径影响报告
- 2024年演出经纪人之演出经纪实务考试题库带解析答案
- 广东绿道工程监理规划
- 一岗双责及新安法重点解读安全教育培训
- 第22课《礼记二则-大道之行也》课件
- 农产品质量安全追溯体系
- 2025届高考物理大一轮复习课件 第六章 第28课时 动能定理在多过程问题中的应用
- 化学●安徽卷丨2024年安徽省普通高中学业水平选择性考试化学试卷及答案
- 2025年全国注册会计师考试审计知识全真模拟试卷及答案(共三套)
- 消防初级试题及答案
- 农场转让合同协议书模板
- 2024-2025学年人教版数学一年级下学期期末模拟试卷(含答案)
- 2025-2030中国共享单车服务行业市场现状供需分析及投资评估规划分析研究报告
- 安徽省合肥一中2025届高三最后一卷英语试题及答案
- 有关工厂实习心得体会模版
- 2025年法律职业资格(客观题)重点考点大全
- 2025年组织行为学专业考试试题及答案
- 不寐的中医护理常规
- 2024年直播电商高质量发展报告
- 创新设计思维
- 客诉处理培训课件
评论
0/150
提交评论