最长单一递增子序列

最长单调递增子序列

设给定的序列为num[n]

1.O(n^2)的求法

动态规划的方法，设dp[i] 表示已num[i]结尾的最长单调递增子序列的长度，求法如下：

void MaxSubsequence(int n)  //求最长递增子序列
{
	int ma=0;
	for(int i=0;i<n;i++)
	{
		dp[i]=1;
		for(int j=0;j<i;j++)
			if(num[j]<num[i] && dp[i]<dp[j]+1)
				dp[i]=dp[j]+1;
		if(ma<dp[i]) ma=dp[i];
	}
	printf("%d\n",ma);
}

2. O(nlogn)的求法

   ind[i] ：长度为i的单调递增子序列的最后一个元素的值

   具体方法为：将num序列的每一个元素插入到ind数组中，插入位置通过二分查找获得，故复杂度为O(nlogn)。

   注意：ind数组中所存储的元素不一定就是符合条件的子序列，但所求的长度却是最大长度

    eg：

    num[]={2,3,5,1}  按照上述方法插入到ind数组中，结果为：1,3,5。

    最长单调递增子序列长度为3，但1,3,5并不是符合要求的序列……

代码实现如下：

int ind[INF]; //ind数组的下标从1开始存数据，这样可以使返回的下表位置正好为子序列的长度
int Find(int l,int r,int val)  //二分查找val应插入的位置
{
	int mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(val>num[mid])
			l=mid+1;
		else if(val<num[mid])
			r=mid-1;
		else return mid;
	}
	return l;
}

void Solve(int n)
{
	for(int i=2;i<=n;i++)
		ind[i]=INF;  //INF为自定义的一个很大的数
	ind[0]=-INF,ind[1]=num[0];
	int ma(-INF);  //记录最大长度
	for(int i=1;i<n;i++)  //时间复杂度为O(n)
	{
		int index=Find(0,n+1,num[i]);  //时间复杂度为O(logn)
		ind[index]=num[i];  //将num[i]插入ind数组
		if(ma<index) //更新最大长度
			ma=index;
	}
	cout<<ma<<endl;
}