最长递增子序列
最长递增子序列问题是一个很基本、较常见的小问题，但这个问题的求解方法却并不那么
显而易见，需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过
的基本的算法分析和设计的方法与思想，能够锻炼设计较复杂算法的思维，我对这个问题进行了
较深入的分析思考，得出了几种复杂度不同算法，并给出了分析和证明。
设L=
Lin= K1k2km12mK1k2km LCS 设序列X= 的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长 公共子序列问题LCS了。 最长公共子序列问题用动态规划的算法可解。设Li=< a,a,…,a >,X j=< b,b,…,b >，12i 12j 它们分别为L和X的子序列。令C[ i, j]为Li与X j的最长公共子序列的长度。这可以用时间复 2杂度为O(n)的算法求解，由于这个算法上课时讲过，所以具体代码在此略去。求最长递增子序 2列的算法时间复杂度由排序所用的O(nlogn)的时间加上求LCS的O(n)的时间，算法的最坏 22时间复杂度为O(nlogn)＋O(n)＝O(n)。 设f(i)表示L中以a末元素的最长递增子序列的长度。则有如下的递推方程：i 这个递推方程的意思是，在求以a为末元素的最长递增子序列时，找到所有序号在L前面且小i 于a的元素a，即j 即以a为末元素的最长递增子序列，等于以使f(j)最大的那个a为末元素的递增子序列最末再ij加上a；如果这样的元素不存在，那么a自身构成一个长度为1的以a为末元素的递增子序列。 iii这个算法由Java实现的代码如下： public void lis(float[] L) { int n = L.length; int[] f = new int[n];//用于存放f(i)值； f[0]=1;//以第a1为末元素的最长递增子序列长度为1； for(int i = 1;i { f[i]=1;//f[i]的最小值为1； for(int j=0;j { if(L[j] f[i]=f[j]+1;//更新f[i]的值。 } } System.out.println(f[n-1]); } 这个算法有两层循环，外层循环次数为n-1次，内层循环次数为i次，算法的时间复杂度 2所以T(n)=O(n)。这个算法的最坏时间复杂度与第一种算法的阶是相同的。但这个算法没有排 序的时间，所以时间复杂度要优于第一种算法。 在第二种算法中，在计算每一个f(i)时，都要找出最大的f(j)(j 只能顺序查找满足a 时间复杂度就可能降到O(nlogn)。于是想到用一个数组B来存储“子序列的”最大递增子序列的 最末元素，即有 B[f(j)] = a j 在计算f(i)时，在数组B中用二分查找法找到满足j lis1(float[] L) { int n = L.length; float[] B = new float[n+1];//数组B； B[0]=-10000;//把B[0]设为最小，假设任何输入都大于-10000； B[1]=L[0];//初始时，最大递增子序列长度为1的最末元素为a1 int Len = 1;//Len为当前最大递增子序列长度，初始化为1； int p,r,m;//p,r,m分别为二分查找的上界，下界和中点； for(int i = 1;i { p=0;r=Len; while(p<=r)//二分查找最末元素小于ai+1的长度最大的最大递增子序列； { m = (p+r)/2; if(B[m] else r = m-1; } B[p] = L[i];//将长度为p的最大递增子序列的当前最末元素置为ai+1; if(p>Len) Len++;//更新当前最大递增子序列长度； } System.out.println(Len); } 现在来证明这个算法为什么是正确的。要使算法正确只须证如下命题： 1每一次循环结束数组B中元素总是按递增顺序排列的。 用数学归纳法，对循环次数ｉ进行归纳。 当i=0时，即程序还没进入循环时，命题显然成立。 设i 是递增的，因此第i次循环时B[j]或B[j]必有一个更新，假设B[j]被更新为元素a，由于121i+1a=B[j]> B[j]，按算法a应更新B[j]才对，因此产生矛盾；假设B[j]被更新，设更新i+112i+122前的元素为s,更新后的元素为a，则由算法可知第i次循环前有B[j]＝s< a< B[j]，这i+12i+11与归纳假设矛盾。命题得证。 2B[c]中存储的元素是当前所有最长递增子序列长度为c的序列中，最小的最末元素， 即设当前循环次数为i，有B[c]={a|f(k)=f(j)=c?k,j?i+1?a?a}(f(i)为与第二种算法中jjk 的f(i)含义相同)。 程序中每次用元素a更新B[c]时(c=f(i))，设B[c]原来的值为s，则必有 a B[c+1]而不是B[c]了。所有i B[c]中存放的总是当前长度为ｃ的最长递增子序列中，最小的最末元素。 3设第i次循环后得到的p为p(i+1)，那么p(i)为以元素a为最末元素的最长递增子序i 列的长度。 只须证p(i)等于第二种算法中的f(i)。显然一定有p(i)<＝f(i)。假设 p(i) 让a接在后面形成长于p(i)的最长递增子序列的元素不在数组B中，由命题2可知，这是不可i 能的，因为B[c]中存放的是最末元素最小的长度为c的最长递增子序列的最末元素，若a能接i在长度为L(L> p(i))的最长递增子序列后面，就应该能接在B[L]后面，那么就应该有p(i)=L,与L> p(i)矛盾。因此一定有p(i)＝f(i)，命题得证。 算法的循环次数为n，每次循环二分查找用时logn，所以算法的时间复杂度为O(nlogn)。这个算法在第二种算法的基础上得到了较好的改进。 本论文只给出了计算解的大小而没有给出构造解的方法，因为我认为计算解的大小的算法已 能给出对问题的本质认识，只要计算解大小的算法设计出，构造解就只是技术细节的问题了，而 我关心的是怎样对问题得到很好的认识而设计出良好的算法。以上几种算法已用Java实现，都能得到正确的结果。在设计和改进算法时用到了基本的算法设计和分析、证明的基本方法，很好 的锻炼了设计与分析算法的思维能力，让我从感性上认识到算法分析与设计的重要性，并且感受 了算法分析、设计和改进的乐趣。 【实验目的】 练习掌握动态规划算法。 【实验内容】 设计一个O(n*n)时间的算法，找出由n个数组成的序列的最长单调递增子序列。 【实验条件】 Microsoft Visual C++ 6.0 【需求分析】 题目要求在O(n*n)的时间内找出n个数组成的序列的最长单调递增子序列,需要 用到排序算法，查找最长公共子序列的算法。 【设计原理】 将数组a复制到数组x,先用排序算法将数组x排序，在调用查找最长公共子序列的算法求出数组a和数组x中的最长公共子序列，因为数组x是单调递增的，所以由此求出来的最长公共子序列就是题设所求的最长单调递增子序列。 【概要设计】 数据： N：数组元素个数。 a[N]：用于存放数组。 X[N]：复制数组a[N]，并排序。 c[i][j]：存储a和x的最长公共子序列的长度。 b[i][j]：记录c[i][j]的值是由哪一个资问题的解得到的。函数： int Partition(int a[],int p,int t,int x); //数组划分，将小于等于x的元素移到x左边，大于x的元素移到x右边。 void Swap(int &x,int &y); //交换元素x和y。 void QuickSort(int a[],int p,int r); //快速排序。 void LCSL(int m,int n,int *x,int *y,int **c,int **b); //计算最长公共子序列长度。 void LCS(int i,int j,int *x,int **b); 根据b[i][j]的内容打印a,x数组的最长公共子序列。 【详细设计】 #include #include using namespace std; #define N 10 void LCSL(int m,int n,int *x,int *y,int **c,int **b);//计算最长公共子 序列长度。 void LCS(int i,int j,int *x,int **b);//根据b[i][j]的内容打印a,x数组的最长公共子序列。 void QuickSort(int a[],int p,int r);//快速排序。 int Partition(int a[],int p,int t);//数组划分，将小于等于x的元素移到 x左边，大于x的元素移到x右边。 void Swap(int &x,int &y);//交换元素x和y。 //计算最长公共子序列长度 void LCSL(int m,int n,int *x,int *y,int c[][N],int b[][N]) { c[0][0]=0; int i,j; for(i=1;i<=m;i++) c[i][0]=0; for(i=1;i<=n;i++) c[0][i]=0; for(i=1;i<=m;i++) for(j=1;j<=m;j++) { if(x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } } cout< } //根据b[i][j]的内容打印a,x数组的最长公共子序列 void LCS(int i,int j,int *x,int b[][N]) { if(i==0||j==0) return; if(b[i][j]==1) { LCS(i-1,j-1,x,b); for(int y=1;y if(x[y]==x[i]) return; cout< } else if(b[i][j]==2) { LCS(i-1,j,x,b); } else LCS(i,j-1,x,b); } void QuickSort(int a[],int p,int r) { if(p { int q=Partition(a,p,r); QuickSort(a,p,q-1);//对左半段排序 QuickSort(a,q+1,r);//对右半段排序 } } int Partition(int a[],int p,int r) { int i=p, j=r+1; int x=a[p]; //将 //将>x的元素交换到右边区域 while(true) { while(a[--j]>x); while((i if(i>=j)break; Swap(a[i],a[j]); } a[p]=a[j]; a[j]=x; return j; } void Swap(int &x,int &y) { int t; t=x; x=y; y=t; } void main(void) { int *a,*x; a=new int[N]; x=new int[N]; int b[N][N]; int c[N][N]; cout<<"请输入十个数："< { cin>>a[i]; x[i]=a[i]; } QuickSort(x,1,N-1); LCSL(N-1,N-1,a,x,c,b); LCS(N-1,N-1,a,b); }
相关主题
文本预览