问题描述:
给出一个数列,找出其中最长的单调递减(或递增)子序列。比如数列 4,2,6,3,1,5 最长递增子数列为2,3,5
相似的问题:1求最大和的子序列
2最大公共子串
3最大公共子序列
注意:串与序列的关系,,串是连续的,而序列则不可以。。。
解决办法
:在网上得到两种解法
解法一:
首先将这个序列进行排序,然后再求出已排序的和未排序的这两个数列最长公共子序列
解法二:就是用动态规划法来解决问题:
我们假设原数列定义为数组a[],然后定义一个数组b[i],表示以a[i]结尾的最长公共子序列的长度,只要求出所有的b[i]数组也就可以确定最长的公共子序列,
那么我们根据已经求出的b[0]--b[i-1],来求b[i]呢,,也就如何求出以a[i]结尾的最大公共子序列的长度呢,
此时在a[0]-a[i-1]范围内,已经求出多个长度的公共子序列,且最大长度的一个序列的长度为s,这个序列的最后一个元素为t,那么
1.如果a[i]<t ,那么当前最大子序列的长度为s+1,而且这个序列的最后一个元素就是a[i],即b[i]=s+1
2.如果a[i]=t,那么这个子序列的长度不变,仍为s,b[i]=s;
3.如果a[i]>t,这时候就会比较的麻烦了,因为a[i]不可能成为长度为s的最长公共子序列的最后一项了,然后与一个长度为s-1的公共子序列的最后一项进行比较。。直至小于某一个长度为s1的子序列的最后一个元素t1,
如果a[i]仍然大于t1,那么就继续向长度更小的子序列的最后一个元素进行比较,知道找到一个合适的子序列长度s2,那么此时b[i]=s2+1;如果a[i]比所有的以求子序列的最后一个元素都大话,那么最后就赋值b[i]=1;即以该元素为结尾的子序列长度为1.
那么如何保存这些已经查找出来的子序列的最后一一个元素呢 ,我们定义一个数组c[],即c[i]就是代表长度为i的当前最长子序列的最后一个元素,我们最终的元素超找比较就是在c[]数组中进行的,b[i]最后可以用于最终的最长子序列的输出。
按照上述的条件得到的c[i]肯定是单调递增或者递减的,如果采用二分查找的话那么时间复杂度为O(n*lgn)..
动态的转移公式为:
假设f(i)代表以a[i]结尾的最长单调自增子序列的长度:
/ f(i-1)+1 , a[i]>a[i-1]
f(i)= --- f(i-1) ,a[i]==a[i-1]
\ max(max({f(j)|a[i]<a[j],i>j}+1),1) ,a[i]<a[i-1]
比如查找 4,2,6,3,1,5 的最长递减子数列过程如下:
最终的数组b[]={1,2,1,2,3,1}
数组c[]={-1,6,5,1,-1,-1,}
具体的算法如下:
void getArray(int *a,int length)
{
int *b=new int[length]; //b[i]表示以a[i]结尾的最长递减子序列的长度
int *c=new int[length];//数组c[i]表示长度为i的递减子序列的末尾值的最大值
int s=1;//s表示目前为止最长单调序列的长度
int k=1;
for(int i=0;i<length;i++)//初始化b
{
b[i]=-1;
}
c[1]=a[0];
for(int j=0;j<length;j++)
{
k=BinFind(c,s,a[j]);
if(k>s)
{
s++;
}
c[k]=a[j];
b[j]=k;
}
print(a,b,s,length);//根据数组b[]来打印最长子序列
}
void print(int *a,int *c,int s,int length)//从后向前查找,并打印出来
{
int i=length;
while(s>0)
{
while(c[i]!=s&&s>0)
{
if(i<=0)
{
break;
}
i--;
}
printf("%d ",a[i]);
s=s-1;
i--;
}
}
下面在来说下几个相关的问题:
1.最大子序列问题
就是求出连续的子序列的和最大,数组中有正数也有负数。。。。这个问题在之前已经描述过了。。
就是遍历数组,保证序列的前面部分的和为大于零
最后比较每个序列的和的大小并选择之
2.最长公共子串(LCS)
这个问题主要是找出两个序列之中相同的最长的连续子串比如:abcad abaad 最长公共子串包括ad与ab
如何解决这个问题呢:
在网上见到一个比较新颖的解决方案:用矩阵的形式,如下:
以一个二维数组来表示对应位置相同的位1,不同的为零
b a b
c 0 0 0
a 0 1
0
b 1
0 1
a 0 1
0
可以看见相同的子序列在一条斜线上都为1.所以最长公共子序列为ab,ba
在这种二位数组中寻找这种相同的元素也是比较困难的,,所以就修改到如下方式:
b a b
c 0 0 0
a 0 1
0
b 1
0 2
a 0 2
0
把斜线上的1加到加到最后一个元素位置上,但是考虑到算法的效率,这样会浪费很多无谓的空间,所以我们使用一维数组来描述二维数组:
定义两个一位数组,我们按行进行初始化,其中一个数组保存上一行的数据,另外一个数组保存当前行的数据,当前行的数据就是通过上一行来进行计算,最后找出最大的值
2.最长公共子串(LCS)
最常用的就是动态规划法:
/ 0 if i<0 or j<0
c[i,j]=--- c[i-1,j-1]+1 if i,j>=0 and xi=xj
\ max(c[i,j-1],c[i-1,j] if i,j>=0 and xi≠xj
使用s[i][j]数列来保存c[i][j]使用上述哪种方式得到的,,,最后找出s[i][j]中所有位1为i,j(即是由i-1,j-1得到的c[i][j])
分享到:
相关推荐
如果已知一个序列中最长的不下降子序列长度,那么这个序列前面添加一个数之后的最长的不下降子序列长度可能加1,这与原来的最长不下降子序列中最大的两个数有关。 具体是,如果加的数比子序列最大值大,长度加1。...
EE课程 数列递增子序列 数据与算法 实验报告
用动态规划实现最长递增子序列的求解,并回溯输出最长公共子序列
第八次作业 k递增子数列.c
求最长不下降序列 求最长不下降序列 求最长不下降序列 求最长不下降序列
给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元 素的情况下,该数组能否变成一个非递减数列。非递减数列定义如下:对 于数组中所有的 i (1 ),满足 array[i] [i + 1]
一个递增的数列,依然可以O(n)内处理,我在 vector的末尾,push_back(0)了一下,导致它不是递增的了
c++最长公共子序列一行最优值最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)...一个数列 ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则称为已知序列的最长公共子序列
给定一个数列,请问数列中最长的递增序列有多长。 输入格式 输入的第一行包含一个整数 n。 第二行包含 n 个整数 a[1], a[2], …, a[n],相邻的整数间用空格分隔,表示给定的数列。 输出格式 输出一行包含一...
例中13,16,18,19,21,22,63就是一个长度为7的不下降序列,同时也有7 ,9,16,18,19,21,22,63组成的长度为8的不下降序列。 【输入】 第一行为n,第二行为用空格隔开的n个整数。 【输出】 第一行为输出最大...
最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子...一个数列 ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则称为已知序列的最长公共子序列。
Java 求出数列前20项的和,有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13...求出这个数列的前20项之和。可以得出规律为:后一个数的分母为前一个数分子和分母之和,因此可以得出计算方法如下: for(int i = 1;i;...
《2的平方根:关于一个数与一个数列的对话》像是一位“老师”与一个“学生”的对话。老师通过一系列问答引导学生,通过一个漂亮而又简单的几何范例,建立了一个关于2的平方根的问答二重奏。博学的老师引导学生一步步...
【问题描述】编写函数f,功能是用递归的方法求斐波那契数列的第n项,函数原型为 int f(int n),在主函数中输入一个正整数n,调用函数f求出斐波那契数列的第n项,并在主函数中输出。 斐波那契数列:1,1,2,3,5,8,13,...
C语言程序设计-求出菲波那契数列的前一项与后一项之比的极限的近似值;例如:当误差为0.0001时,函数值为0.618056;
# 题目: # 有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13...求出这个数列的前20项之和。 # 分析: # 请抓住分子与分母的变化规律。
Fibonacci数列,用c++编写的,非递归的函数调用求Fibonacci数列的第n项
包含动态规划解决斐波那契数列优化方法,以及动态规划获取最长公共子序列方法
使用C++非递归实现fibonacci数列,对正在学习算法的同学应该挺有帮助的
Sologala @github [665]非递减数列| non-decreas