最长递增子序列（输出最长递增序列 及其长度）
发布时间
阅读量：
阅读量
解决最长递增子序列问题的方法多种多样。常见的包括LCS算法、动态规划以及通过记录所有递增子序列的最大长度来确定最优解的方法。
采用最长公共子序列法的方式进行处理时，则对给定的数据集合进行排序处理得到一个新的有序数据集 A' ；接着通过比较原始数据集 A 与其排序后的版本 A' 来确定它们之间的最大共同子序列。其中可以观察到两者的最大共同子序列为\{\dots\}（具体数值），这正是原始数据集的最大递增子序列。
在
动态规划 ：参见http://qiemengdao.iteye.com/blog/1660229
这里主要介绍第三种方法：时间复杂度O(n lgn)
初始化一个数组MaxV[i]用于存储所有长度为i的递增子序列的最大元素。对于每个元素a[k]在数组中依次处理：如果当前元素a[k]大于前一个长度（即len-1）对应的MaxV值，则将长度len递增并更新MaxV[len]为当前元素a[k]。
除此之外，在MaxV数组中由后往前寻找第一个大于a_k的位置j（即长度j的最大递增子序列的最大值应被设定为此处a_k），并将a_j替换为此处a_k）。在查找过程中可采用二分法
我们为了记录最大递增序列而设置了变量maxIndex来记录其索引位置；特别地，在初始化阶段需将maxIndex[0]设为0；当遇到当前元素a[k]大于当前最大值MaxV[len-1]时，则会自动触发更新操作；同时，在当前元素a[k]小于当前最大值MaxV[len-1”的情况下（尤其是当pos等于len-1时），也需要考虑是否需要更新maxIndex的值
因此该博客中的解决方案存在缺陷，并已修复
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 else
34 {
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,10
54 };
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 }全部评论 (0)
还没有任何评论哟~