动态规划：最长上升子序列

╰半橙微兮° 2022-01-22 09:23 252阅读 0赞

1.1 朴素方法 O（n ^2）:

思路：每个数都遍历他前面的所有数，如果这个数比前面的数要大，更新他自己或者他前面的数+1的最大的一个数。

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int mmax=1e6+10;
    ll dp[mmax],a[mmax];
    int main()
    {
    	 ll n;
    	 cin>>n;
    	 for(int i=0;i<n;i++)
    	  	cin>>a[i];
    	 ll ans=0;
    	 for(int i=0;i<n;i++)
    	 {
    		  dp[i]=1;
    		  for(int j=0;j<i;j++)
    		  {
    			   if(a[i]>a[j])
    			   	 dp[i]=max(dp[i],dp[j]+1);
    		  }
    		  ans=max(ans,dp[i]);
    	}
    	 cout<<ans<<endl;
    	 return 0;
    }

2.1 二分lis O（n\* log n）:

思路：朴素方法是每个数每次都会与其他数比较大小，浪费时间，所以二分找他第一个比他大的数。lis 数组里的数代表的是最长上升子序列长度的最后一个数，数组长度就是最长上升子序数的长度，注意，lis数组里的数不是最长上升子序数的所有数。两种情况，如果这个数比lis数组里的数大，直接加入lis数组，len++；否则二分找他第一个比他大的数，替换他。

写法1：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const ll mmax=1e6+10;
    ll a[mmax],lis[mmax];
    ll len; 
    ll find(ll x)
    {
    	 ll l=0,r=len;
    	 while(l<r)
    	 {
    		  ll mid=(l+r)>>1;
    		  if(lis[mid]>=x)
    		  	 r=mid;
    		  else
    		   	l=mid+1;
    	}
    	 return l;
    }
    int main()
    {
    	 ll n;
    	 memset(a,0,sizeof(a));
    	 memset(lis,0,sizeof(lis));
    	 cin>>n;
    	 for(int i=0;i<n;i++)
    	  	cin>>a[i]; 
    	 lis[0]=a[0];
    	 len=0;
    	 for(int i=1;i<n;i++)
    	 {
    		  if(a[i]>lis[len])
    		  {
    		   	lis[++len]=a[i]; 
    		  }
    		  else
    		  {
    		   	ll k=find(a[i]);
    		   	lis[k]=a[i];
    		  } 
    	} 
    	cout<<len+1<<endl;
    	 return 0;
    }

写法2：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int mmax=1e6+10;
    int a[mmax],lis[mmax];
    int main()
    {
    	 ll n;
    	 memset(a,0,sizeof(a));
    	 memset(lis,0,sizeof(lis));
    	 cin>>n;
    	 for(int i=0;i<n;i++)
    	  	cin>>a[i];
    	 lis[0]=a[0];
    	 ll len=0;
    	 for(int i=1;i<n;i++)
    	 {
    		  if(a[i]>lis[len])
    		  {
    		   	lis[++len]=a[i]; 
    		  }
    		  else
    		  {
    		   	ll k=upper_bound(lis,lis+len,a[i])-lis;
    		   	lis[k]=a[i];
    		  } 
    	 } 
    	 cout<<len+1<<endl;
    	 return 0;
    }