最长上升子序列的两种求法 POJ 2533-白红宇

最长上升子序列的两种求法 POJ 2533

阅读量：3905 次

发布时间：2019-05-23

本文共 995 字，大约阅读时间需要 3 分钟。

最长上升子序列一共有两种求法：

1.dp，也可以说的纯暴力吧。

dp[i]表示以a[i]为结尾的最长上升子序列的长度。

所以只要满足j<i且a[j]<a[i]，则一定满足dp[j]=max(dp[j],dp[i]+1);

复杂度为n^2;

2.是在上述方法的优化，建一个dp数组。

dp[i]表示长度为i的上升子序列中末尾元素的最小值。

因为dp数组一定是有序的，这样每次插入元素的时候可以结合二分查找使效率更高。

复杂度为logn*n;

例题为poj 2533

1.第一种方法：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=1e3+5;int n;int a[maxn];int dp[maxn];int main(){	scanf("%d",&n);	for (int i=1;i<=n;i++) scanf("%d",&a[i]);	for (int i=1;i<=n;i++) dp[i]=1;	int Max=1;	for (int i=1;i<=n;i++)	{		for (int j=i+1;j<=n;j++)		{			if(a[i]

注意初始化Max=1。

2.第二种方法：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=1e3+5;int n;int a[maxn];int dp[maxn];int len;int main(){	scanf("%d",&n);	len=0;	for (int i=1;i<=n;i++) scanf("%d",&a[i]);	for (int i=1;i<=n;i++)	{		int loc=lower_bound(dp,dp+len,a[i])-dp;		if(loc==len) dp[len++]=a[i];		else 		{			dp[loc]=a[i];		}	}	printf("%d\n",len);	return 0;}