首页 > 代码库 > 最长递增子序列（输出最长递增序列 及其长度）
最长递增子序列（输出最长递增序列 及其长度）
最长递增子序列的解法有很多种，常用的有最长公共子序列法、动态规划、记录所有递增序列长度最大值的方法。
最长公共子序列法：如例子中的数组A{5，6， 7， 1， 2， 8}，则我们排序该数组得到数组A‘{1， 2， 5， 6， 7， 8}，然后找出数组A和A’的最长公共子序列即可。显然这里最长公共子序列为{5, 6, 7, 8}，也就是原数组A最长递增子序列。
在http://blog.csdn.net/yysdsyl/article/details/4226630中有详细解释。
动态规划：参见http://qiemengdao.iteye.com/blog/1660229
这里主要介绍第三种方法：时间复杂度O(n lgn)
维护一个数组MaxV[i]，记录所有长度为i的递增子序列中最大元素的最小值。
思路：遍历数组，如果数组中该元素a[k]大于MaxV[len-1]的值，直接len++，MaxV[len]=a[k]；
否则从MaxV中从后向前，找到第一个比a[k]大的值的索引j，并将MaxV[j]更新为a[k]（即长度为j的递增序列最大值的最小值应为a[k]），查找过程可以使用二分搜索。
为了记录最大递增序列，我们使用maxIndex记录其索引，注意需要初始化maxIndex[0]=0；在a[k]>MaxV[len-1] 和 a[k]<MaxV[len-1]&&pos==len-1时，都需要更新maxIndex的值。
所以博客http://blog.csdn.net/imzoer/article/details/8100064的解法是有问题的，这里已经更正。
1 //修改后的二分搜索，返回从后向前，第一个比target大的索引 2 int bsearch(int *a, int s, int e,int target) 3 { 4 while(s<=e) 5 { 6 int mid = s +(e-s)/2; 7 if(a[mid]<=target) 8 { 9 s=mid+1;10 }11 else 12 {13 e = mid-1;14 }15 }16 return s;17 }18 int getMaxSub(int *a, int n)19 {20 int *maxIndex = new int[n];21 int *maxV = new int[n];22 int len =1;23 maxV[0] = a[0];24 maxIndex[0]=0;25 for(int i=1; i <n; i++)26 {27 if(a[i]>maxV[len-1])28 {29 maxV[len]=a[i];30 maxIndex[len]=i;31 len++;32 }33 else34 {35 int pos = bsearch(a,0,len-1,a[i]);36 maxV[pos]= a[i];37 if(pos == len-1)38 maxIndex[pos]=i;39 }40 }41 for(int i=0;i<len;i++)42 {43 printf("%d\t",a[maxIndex[i]]);44 }45 printf("\n");46 return len;47 } 48 int main()49 {50 51 52 int a[]={53 7,5,4,2,3,5,6,1,5,8,9,1054 };55 int b[]={56 1, 5, 8, 3, 6, 7, 2, 9 57 };58 printf("The array is :\n");59 for(int i=0;i<12;i++)60 {61 printf("%d\t",a[i]);62 }63 printf("\nThe max ascending array is:\n");64 printf("The length of max ascending array is :%d\n",getMaxSub(a,12));65 //getMaxSub(b,8);66 67 }
最长递增子序列（输出最长递增序列 及其长度）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。