15 动态规划-最长上升子序列

问题描述:给出一个序列a1,a2,a3,a4,a5,a6,a7….an,求它的一个子序列（设为s1,s2,…sn），使得这个子序列满足这样的性质，s1<s2<s3<…<sn并且这个子序列的长度最长，输出这个最长的长度。

例如有一个序列:1 7 3 5 9 4 8,它的最长上升子序列就是 1 3 4 8 长度为4

算法一（时间复杂度为O(n^2)）：

该算法的思想是，计算每一个a[i]为结尾元素的上升子序列，存入dp[i]，则dp[i]中的最大值即为最长上升子序列

int dp[1000];
int LIS(int arr[1000], int n)
{
	dp[1]=1;
	for(int i=2; i<=n; i++)
		dp[i]=0;
	int ans;
	for(int i=2; i<=n; i++)
	{
		ans=0;
		for(int j=1; j<i; j++)
		{
			if(arr[i]>arr[j] && dp[j]>ans)
				ans=dp[j];
		}
		dp[i]=ans+1;
	}
	ans=0;
	for(int i=1; i<=n; i++)
	{
		if(dp[i]>ans)
			ans=dp[i];
	}
	return ans;
}

算法二（时间复杂度为O(nlgn)）：

该算法的思想是，建立一个辅助数组b[]，b[1]=1，表示只有一个元素时LIS为1,；b[i]的值动态更新为满足LIS为 i 时，源数据中的最小值(这句话有点晦涩，细细体会)

int bSearch(int num, int k)  
{  
    int low=1, high=k;  
    while(low<=high)  
    {  
        int mid=(low+high)/2;  
        if(num>=b[mid])  
            low=mid+1;  
        else   
            high=mid-1;  
    }  
    return low;  
}  
 
int LIS()
{
	int low = 1, high = n;
	int k = 1;
	b[1] = p[1];
	for(int i=2; i<=n; ++i)
	{
		if(p[i]>=b[k])
			b[++k] = p[i];
		else
		{
			int pos = bSearch(p[i], k);
			b[pos] = p[i];
		}
	}
	return k;
}

(责任编辑：admin)