现在的位置: 首页 > 综合 > 正文

最长单调递增子序列

2012年06月13日 ⁄ 综合 ⁄ 共 1825字 ⁄ 字号 评论关闭

题目:给定一个序列X[0···n],找出它的最长的单调递增子序列(Longest Increasing Subsequence)

分析:

思路一:

        将序列X按非递减顺序排列,形成新序列Y,问题就转变成求解X和Y的LCS。

假设使用快速排序,则排序过程的时间复杂度为O(nlgn),而求两个序列的LCS的时间复杂度为O(n2)(因为X、Y长度相等),综合可知该解法的时间复杂度为O(n2)。

思路二:

        对于X[0···n]中的每一个元素xi,求出以它结尾的X[0···i]的LIS,保存在数组lis中,然后找出lis中最大的元素,即X[0···n]的LIS。

假设求X[0···i]的LIS,即求lis[i],那么在X[0···i-1]寻找x0,x1,···,xi-1中所有小于xi的元素xj(0 <= j <= i-1 ),对于每一个xj,都有一个以它结尾的序列X[0···j]的最长单调递增子序列,其长度自然为lis[j],然后从这些lis[j]找出最大的元素,那么lis[i]就等于这个lis[j]加1,这就是X[0···i]的LIS。而如果X[0···i-1]中没有小于xi的元素,那么lis[i]等于1.

由此可以得到递归方程:

                  0    i == 0

  Lis[i] =      

                   max( lis[j] + 1, 1 )    X[j] < x[i] && j < i

该解法的时间复杂度为O(n2)。

思路三:

                假设 result数组保存以X[i]结尾的最长递增子序列的长度,X的LIS的长度为K。由于长度为i( 1 <= i <= k )的LIS可能不止一个,那么我们用数组minInMax记录下长度相同的LIS的末尾元素中的最小值。

如果X[i] 大于 minInMax[ result[i-1] ] ,那么result[i] = result[i-1] +1,否则,result[i]与result[i-1]相等。由于minInMax是递增的,所以使用二分查找确定array[i]应该放在哪个位置上。

              与思路二相比,思路三使用二分查找代替了顺序查找,使时间复杂度由o(n2)提高到了o(nlgn)。

 

思路二算法

int lis( vector<int> array, vector<int> result )
{
	int i, j;
	for( i = 0; i < LENGTH; ++i )
	{
		result[i] = 1;
		for( j =0; j < i; ++j )
		{
			if( array[j] < array[i] && result[j] + 1 > result[i] )
			{
				result[i] = result[j] + 1;
			}
		}
	}
	return  maximum( result );//result存储以array[i]为末尾元素的LIS的长度,所以result数组的最大值即array的LIS的长度
}

 思路三算法:

//result存储最长单调递增子序列的长度,minInMax存储长度为i的最长递增子序列中的末尾元素中的最小值
void lis2( vector<int> &array, vector<int> &result )
{
	vector<int> minInMax( array.size() );
	int i,low,high,mid;
	result[0] = 1;
	minInMax[ result[0] ] = array[0];

	for( i = 1; i < array.size(); ++i )
	{
		if( array[ i ] > minInMax[ result[i-1] ] )//当前元素值大于array[0···i-1]序列中最长递增子序列中的最大值的最小值
		{
			result[i] = result[i-1] + 1;
			minInMax[ result[i] ] = array[i];
		}else
		{
			result[i] = result[i-1];
			low = 0;
			high = result[i-1];
			mid = (low + high)/2;
			while( low <= high )//由于minInMax是递增的,所以使用二分查找确定array[i]应该放在哪个位置上
			{
				if( array[i] > minInMax[mid] )
				{
					low = mid + 1;
				}else{
					high = mid - 1;
				}
				mid = (low+high)/2;
			}
			minInMax[low+1] = array[i];
		}
	}
}

程序文件,点击这里

 

抱歉!评论已关闭.