最长递增子序列问题的求解
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想,能够锻炼设计较复杂算法的思维,我对这个问题进行了较深入的分析思考,得出了几种复杂度不同算法,并给出了分析和证明。
一, 最长递增子序列问题的描述
设L=<a1,a2,…,an>是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>,其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
二, 第一种算法:转化为LCS问题求解
设序列X=<b1,b2,…,bn>是对序列L=<a1,a2,…,an>按递增排好序的序列。那么显然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。
最长公共子序列问题用动态规划的算法可解。设Li=< a1,a2,…,ai>,Xj=< b1,b2,…,bj>,它们分别为L和X的子序列。令C[i,j]为Li与Xj的最长公共子序列的长度。则有如下的递推方程:
这可以用时间复杂度为O(n2)的算法求解,由于这个算法上课时讲过,所以具体代码在此略去。求最长递增子序列的算法时间复杂度由排序所用的O(nlogn)的时间加上求LCS的O(n2)的时间,算法的最坏时间复杂度为O(nlogn)+O(n2)=O(n2)。
三, 第二种算法:动态规划法
设f(i)表示L中以ai为末元素的最长递增子序列的长度。则有如下的递推方程:
这个递推方程的意思是,在求以ai为末元素的最长递增子序列时,找到所有序号在L前面且小于ai的元素aj,即j<i且aj<ai。如果这样的元素存在,那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j),把其中最大的f(j)选出来,那么f(i)就等于最大的f(j)加上1,即以ai为末元素的最长递增子序列,等于以使f(j)最大的那个aj为末元素的递增子序列最末再加上ai;如果这样的元素不存在,那么ai自身构成一个长度为1的以ai为末元素的递增子序列。
四, 对第二种算法的改进
在第二种算法中,在计算每一个f(i)时,都要找出最大的f(j)(j<i)来,由于f(j)没有顺序,只能顺序查找满足aj<ai最大的f(j),如果能将让f(j)有序,就可以使用二分查找,这样算法的时间复杂度就可能降到O(nlogn)。于是想到用一个数组B来存储“子序列的”最大递增子序列的最末元素,即有
B[f(j)] = aj
在计算f(i)时,在数组B中用二分查找法找到满足j<i且B[f(j)]=aj<ai的最大的j,并将B[f[j]+1]置为ai。
代码如下:
#include <iostream>
#define LEN 6
using namespace std;
void show(int a[],int N)
{
for(int i=0; i<N; i++) cout<<a[i]<<" ";
cout<<endl;
}
void findMaxLen(int a[],int f[],int n,int len)
{
int i,max=0;
if(n>0)
{
for(i=n-1;i>=0;i--)
{
if(a[i]<=a[n]&&f[i]>=max) max =f[i];
}
}
else{
f[n] = 1;
}
if(max!=0){
f[n] = max + 1;
}
else f[n]=1;
}
int main()
{
int a[LEN]={1,3,4,2,7,5};
int f[LEN]={0};
int max =0;
/* 没有改进的O(n2)
for(int i=0;i<LEN;i++)
{
findMaxLen(a,f,i,5);
if(f[i]>=f[max])max =i;
}
cout<<a[max]<<endl;
show(f,LEN);
*/
//改进后的O(nlogn)
int b[LEN]={0};
b[0] = -10000;
b[1] = a[0];
int maxLen=1;
for(int i=1;i<LEN;i++)
{
int mid,left=0,right=maxLen;
while(left<=right)
{
mid = (left+right)/2;
if(b[mid]<a[i])left = mid+1;
else right = mid-1;
}
b[left] = a[i];
if(left > maxLen) maxLen++;
}
cout<<maxLen<<endl;
show(b,LEN);
}
分享到:
相关推荐
这是我这两天才完成的原创代码,就是比较经典的求一个随机序列的最长递增子序列问题。例如: n=5 随机序列为 5 1 4 2 3,正确输出为1 2 3,即长度为3的递增子序列。里面附带实验详细说明,感兴趣的可以下来参考。 ...
求一个由n个整数组成的整数序列的最长递增子序列。一个整数序列的递增子序列可以是序列中非连续的数按照原序列顺序排列而成的。 最长递增子序列是其递增子序列中长度最长的。
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
动态规划最长递增子序列 已经实现 请大家赐教
最长子序列 什么是最长递增子序列呢? 问题描述如下: 设L=,a2,…,an>是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=,ak2,…,akm>,其中k1…且aK1…。求最大的m值
最长递增子序列LCS的实现C源码,大学算法导论课程实验
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 Visual Studio 2012 项目包 使用4种不同的方法实现最长递增子序列
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想,...
算法课实验代码,包括整数划分、各类排序、最长递增子序列、幻方矩阵等试验
贪心算法、动态规划实现最长递增子序列的求取(MFC编程)。
动态规划:最长单调递增子序列 A numeric sequence of ai is ordered if a1 (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 , sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. ...
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 实验报告 使用4种不同的方式实现最长递增子序列
中国科学技术大学软件学院《算法设计与分析》实验题目四
给你一个整数数组 nums ,找到...解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。 示例 2: 输入:nums = [0,1,0,3,2,3] 输出:4 示例 3: 输入:nums = [7,7,7,7,7,7,7] 输出:1 参数范围: 1 -104 [i] <=104
最长递增子序列的另外一种C语言实现代码,大学算法导论课程实验
C++的课程作业,一个简单的程序,用dev就能直接运行,老师应该不会太仔细检查,糊弄一下肯定没事的,不过最好能自己看懂就是了
包括排序 最长递增子序列 红黑树三个相关程序
这是递增子序列的java实现版 希望对大家有所启迪