【数据结构】数组中的最大连续递增子序列

数组中的数是乱序的，求出数组中最大的连续子序列（这里为递增）。

方法一：用一个辅助数组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");
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!