此前在动态规划一讲:动态规划(3)-最长递增子序列 曾说过此问题,当前是的双重循环是O(n^2)的复杂度。
后来在网上看到说LIS问题有O(nlogn)的算法,于是拿来小研究了一下。
这个算法其实已经不是DP了,有点像贪心。至于复杂度降低其实是因为这个算法里面用到了二分搜索。本来有N个数要处理是O(n),每次计算要查找N次还是O(n),一共就是O(n^2);现在搜索换成了O(logn)的二分搜索,总的复杂度就变为O(nlogn)了。
这个算法的具体操作如下(by RyanWang):
开一个栈,每次取栈顶元素top和读到的元素temp做比较,如果temp > top 则将temp入栈;如果temp < top则二分查找栈中的比temp大的第1个数,并用temp替换它。 最长序列长度即为栈的大小top。
这也是很好理解的,对于x和y,如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y],此时的最长序列长度没有改变但序列Q的”潜力”增大了。
举例:原序列为1,5,8,3,6,7
栈为1,5,8,此时读到3,用3替换5,得到1,3,8; 再读6,用6替换8,得到1,3,6;再读7,得到最终栈为1,3,6,7。最长递增子序列为长度4。
用该算法完成POJ2533的具体代码如下:
#include <iostream> #define SIZE 1001 using namespace std; int main() { int i, j, n, top, temp; int stack[SIZE]; cin >> n; top = 0; /* 第一个元素可能为0 */ stack[0] = -1; for (i = 0; i < n; i++) { cin >> temp; /* 比栈顶元素大数就入栈 */ if (temp > stack[top]) { stack[++top] = temp; } else { int low = 1, high = top; int mid; /* 二分检索栈中比temp大的第一个数 */ while(low <= high) { mid = (low + high) / 2; if (temp > stack[mid]) { low = mid + 1; } else { high = mid - 1; } } /* 用temp替换 */ stack[low] = temp; } } /* 最长序列数就是栈的大小 */ cout << top << endl; //system("pause"); return 0; }
这其中用到了二分查找第一个大于等于的,其实C++里面的有一个函数可用代替二分。
lower_bound 函数
下面是使用lower_bound优化最长上升子序列。由于长度相同的上升子序列只需要保存结尾最小的那个,而长度递增时,结尾数字的大小也是递增的。最长上升子序列就是找出比他大的第一个数。前面的数都比他小,所以他和这个数的长度相同。然后由于他比较然后小,更新找到的那个值。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int num[10]={3,6,3,2,4,6,7,5,4,3}; const int INF=0x3f3f3f3f; int l=10; int g[100]; int d[100]; int main() { fill(g,g+l,INF); int max_=-1; for(int i=0;i<l;i++) { int j=lower_bound(g,g+l,num[i])-g; d[i]=j+1; if(max_<d[i]) max_=d[i]; g[j]=num[i]; } printf("%d\n",max_); return 0; } 此前在动态规划一讲:动态规划(3)-最长递增子序列 曾说过此问题,当前是的双重循环是O(n^2)的复杂度。 后来在网上看到说LIS问题有O(nlogn)的算法,于是拿来小研究了一下。 这个算法其实已经不是DP了,有点像贪心。至于复杂度降低其实是因为这个算法里面用到了二分搜索。本来有N个数要处理是O(n),每次计算要查找N次还是O(n),一共就是O(n^2);现在搜索换成了O(logn)的二分搜索,总的复杂度就变为O(nlogn)了。 这个算法的具体操作如下(by RyanWang): 开一个栈,每次取栈顶元素top和读到的元素temp做比较,如果temp > top 则将temp入栈;如果temp < top则二分查找栈中的比temp大的第1个数,并用temp替换它。 最长序列长度即为栈的大小top。 这也是很好理解的,对于x和y,如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y],此时的最长序列长度没有改变但序列Q的”潜力”增大了。 举例:原序列为1,5,8,3,6,7 栈为1,5,8,此时读到3,用3替换5,得到1,3,8; 再读6,用6替换8,得到1,3,6;再读7,得到最终栈为1,3,6,7。最长递增子序列为长度4。 用该算法完成POJ2533的具体代码如下: #include <iostream> #define SIZE 1001 using namespace std; int main() { int i, j, n, top, temp; int stack[SIZE]; cin >> n; top = 0; /* 第一个元素可能为0 */ stack[0] = -1; for (i = 0; i < n; i++) { cin >> temp; /* 比栈顶元素大数就入栈 */ if (temp > stack[top]) { stack[++top] = temp; } else { int low = 1, high = top; int mid; /* 二分检索栈中比temp大的第一个数 */ while(low <= high) { mid = (low + high) / 2; if (temp > stack[mid]) { low = mid + 1; } else { high = mid - 1; } } /* 用temp替换 */ stack[low] = temp; } } /* 最长序列数就是栈的大小 */ cout << top << endl; //system("pause"); return 0; }
相关推荐
输入序列,求最长上升子序列的长度,算法复杂度nlgn
动态规划解决LIS问题的一种常见方法是使用一个数组来记录以每个元素结尾的最长上升子序列的长度。假设我们有一个数组 `nums`,其中 `dp[i]` 表示以 `nums[i]` 结尾的最长上升子序列的长度。那么我们可以按照以下步骤...
最长上升子序列(Longest Increasing Subsequence,简称 LIS)是一个经典的动态规划问题。给定一个无序的整数数组,找到其中最长上升子序列的长度。 上升子序列指的是一个子序列,它的每个元素都严格大于它前面的...
检验仪器与信息系统的权威标准,200美刀买的,CLSI标准LIS-A1分析仪器与信息系统底层接口规范:Standard Specification for Low-Level Protocol to Transfer Messages Between Clinical Laboratory Instruments and...
在LIS问题中,我们可以定义一个数组dp,其中dp[i]表示以数组中第i个元素为结尾的最长上升子序列的长度。初始化时,每个元素自身都构成一个长度为1的上升子序列,因此dp[i]至少为1。 接下来,我们遍历数组中的每个...
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 Visual Studio 2012 项目包 使用4种不同的方法实现最长递增子序列
我写的LIS算法,有两种思路,程序全在这个cpp文件中,可以运行
LIS-------------------------临床检验信息系统LIS工作流程
LIS------------------------------210种仪器联机设置
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 实验报告 使用4种不同的方式实现最长递增子序列
Enabling Large Intelligent Surfaces with Compressive Sensing and Deep Learning
使用动态规划思想求出最长单调递增子序列(LIS),时间复杂度为O(n log k)
此帮助文件对仪器设置操作等进行总结,方便实施联机,目前只对部分仪器进行了整理,包括通讯设置,接线方式等。
ADVIA Centaur CP LIS-Interface-Guide.pdf,检验仪器联机文档,支持双向通讯,希望对LIS开发工程师有用
##算法最长递增子序列时间复杂度O(nlogn)##接口JAVA swing ##功能更改输入字符串的长度随机生成输入字符串标记输入字符串中最长的递增子序列
1. 定义状态: 2. 状态转移方程: 3. 初始化: 4. 输出: 5. 空间优化: 1 .定义新状态: 2. 状态转移方程: 3. 初始化: 4. 输出:
还提供了一个用于区分列表的功能,该功能利用了 LIS 算法。
探讨了生物信息挖掘中ó模式子序列问题的一个特例,即最长递增子序列(LIS)问题。对于LIS问题,分别用LCS算法、动态规划、动态规划结合二分法进行求解,并分析了这三种算法的时间和空间复杂度,对其中两种算法进行了...
LIS源码-WORD,代码分享,LIS源码-WORD,代码分享LIS源码-WORD,代码分享LIS源码-WORD,代码分享
下面小编就为大家带来一篇LIS 最长递增子序列 Java的简单实现。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧