最长上升子序列模板（LIS）

意思

就是求一个数组的最大上升子序列

模板1

用动态规划来求嗯这里不再过多解释，哔哩哔哩董晓算法老师讲得非常好可以看看

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int m[200010],dp[200010]; 
signed main()
{
	IOS
	int T=1;
	//cin>>T;
	while(T--)
	{
		int ma=0,n;
		cin>>n;
		for(int i=1;i<=n;i++)
		   dp[i]=1;
		for(int i=1;i<=n;i++)
		cin>>m[i];
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
			{
				if(m[i]>m[j])
				dp[i]=max(dp[j]+1,dp[i]);
			}
			ma=max(ma,dp[i]);
		}
		cout<<ma<<endl;
	}
	return 0;
}

模板2

用二分来求嗯这里不再过多解释，这个也是董晓算法老师讲的比较好

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int a[200010],b[200010],t;
signed main()
{
	IOS
	int T=1;
	//cin>>T;
	while(T--)
	{
		int n,cnt=0;;
		cin>>n;
		for(int i=1;i<=n;i++)
		cin>>a[i];
		for(int i=1;i<=n;i++)
		{
			if(a[i]>b[cnt])
			b[++cnt]=a[i];
			else
			{
				int l=0,r=cnt;
				while(l<r)
				{
					int mid=(l+r)/2;
					if(b[mid]>=a[i])
					r=mid;
					else
					l=mid+1; 
				}
				b[r]=a[i];
			}
		}
		cout<<cnt<<endl;
	}
	return 0;
}

用动态规划来写的话时间复杂度是O(n²),如果范围比较大一点的题就会超时，所以可以用模板2来写二分写的话时间复杂度是O(n*logn)