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

前端之家收集整理的这篇文章主要介绍了【数据结构】数组中的最大连续递增子序列前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

数组中的数是乱序的,求出数组中最大的连续子序列(这里为递增)。

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

运行结果为:

原文链接:https://www.f2er.com/datastructure/383083.html

猜你在找的数据结构相关文章