LIS（最长上升子序列）

在一段序列中，我们需要求出最长的上升子序列的长度，我们可以使用动态规划来进行统计

在遍历数据是，不断的与其前面的书进行比较，如果符合条件，就将长度加一并统计

动态规划版

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN = 100005;

int num[MAXN];
int DP[MAXN];

int main()
{
	int n;
	while(~scanf("%d", &n))
	{
		for(int i = 1; i <= n; i++)
		{
			scanf("%d", &num[i]);
			DP[i] = 1;
		}
		int ans = 1;
		for(int i = 2; i <= n; i++)
		{
			for(int j = 1; j < i; j++)
			{
				if(num[i] > num[j])
					DP[i] = max(DP[i], DP[j] + 1);
			}
			ans = max(ans, DP[i]);
		}
		printf("%d\n", ans);
	}
	return 0;
}
           

也可以不断的统计当前的数值能否大于临时数组最大值，加入临时数组末尾或者替换掉临时数组中第一个大于它的数值，最后统计临时数组的长度

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 100005;
int num[MAXN];
int DP[MAXN];

int main()
{
	int n;
	while(~scanf("%d", &n))
	{
		for(int i = 1; i <= n; i++)
			scanf("%d", &num[i]);
			
		int ans = 1;
		DP[1] = num[1];
		for(int i = 2; i <= n; i++)
		{
			if(num[i] > DP[ans])
			{
				ans++;
				DP[ans] = num[i];
			}
			else
			{
				for(int j = 1; j <= i; j++)
				{
					if(DP[j] > num[i])
					{
						DP[j] = num[i];
						break;
					}
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}
           

可是在数据大一点的时候会超时，我们可以用二分优化一下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 100005;

int num[MAXN];
int DP[MAXN];

int main()
{
	int n;
	while(~scanf("%d", &n))
	{
		for(int i = 1; i <= n; i++)
			scanf("%d", &num[i]);

		int ans = 1;
		DP[1] = num[1];
		for(int i = 2; i <= n; i++)
		{
			if(num[i] > DP[ans])
				DP[++ans] = num[i];
			else
			{
				int s = lower_bound(DP + 1, DP + ans + 1, num[i]) - DP; //找到DP中第一个大于等于num[i]的位置，用a[i]替换之
				DP[s] = num[i];
			}
		}
		printf("%d\n", ans);
	}

	return 0;
}
           

这里用到了lower_bound（）函数，这个函数可以找到第一个大于等于某数值的地址，非常好用