数组中的数是乱序的,求出数组中最大的连续子序列(这里为递增)。
方法一:用一个辅助数组list[length],记录下数组中每个元素对应的最大连续序列长度,默认为1,即从该元素后没有连续的序列。当i元素比i-1个元素大时,则将i-1个元素的最大子序列长度加1即为第i个元素的最大序列长度。最后从list[]数组中找到最大的值max,即为该数组的最大连续子序列。
该方法的优点是思路清晰,代码简介易懂;缺点是需要一个额外的数组空间list[].算法的复杂度为O(n*n).
#include<iostream> using namespace std; int List_length(int a[],int length) { int *list = new int[length]; int i,j; list[0] = 1; for(i=1;i<length;++i) { j = i-1; list[i] = 1; if(a[i]>a[j] )//&& list[j]+1>list[i] list[i] = list[j]+1; } int max = 0; for(i=0;i<length;++i) { if(list[i]>max) max = list[i]; } return max; } void main() { int a[5] = {-2,-1,3,4,0}; int num = List_length(a,5); cout<<"The Maximum subsequence's length is:"<<num<<endl; system("pause"); }
运行的结果为:
方法二:采用两个指针p,q遍历数组,从第一个元素开始,p指向第一个元素,q指向p的下一个元素,如果数组是递增的,则q依次++后移,用max记录递增区间。当遇到不再是递增的区间时,判读此时q-1到p之间的区间长度是否大于max,更新max。将p移动到q的位置,q再依次的后移进行比较。当q移动到数组最后时还是递增的,则判断q和p之间的长度是否大于max,更新max。期间可以用i,j来记录最长区间的起始和终止位置。
该方法的时间复杂度更低,而且不需要额外的数组空间,只需一个Max进行记录最大区间长度。而且可以记录下最大区间的起始和终止位置,输入该段子区间。
#include<iostream> using namespace std; int i,j; int List_length(int a[],int length) { int max=0; int p=0,q; for(q=1;q<length;++q) { if((a[q]<a[q-1]))//当不再是递增的时候,这里两数相等的情况没有考虑 { if((q-1-p)>max)//新的递增长度比原来递增的长度长时,修改保存的数;长度相等的情况也没有考虑 { i=p; j=q-1; max=j-i+1; } p=q;//将p指向新的起点 } else if(q==length-1)//判断q走到结束的时候,前面是乱序,后面是递增的情况。 { if(q-p+1>max) { i=p; j=q; max=j-i+1; } } /* else if((q-p)==length-1)//这里是全部都是递增的情况 { i=p; j=q; max=j-i+1; }*/ } return max; } void main() { int a[7] = {10,5,6,0}; int max = List_length(a,7); cout<<"The Maximum subsequence's length is:"<<max<<endl; cout<<"The Maximum subsequence is:"; for(int n=i;n<=j;++n) cout<<a[n]<<" "; system("pause"); }
运行结果为: