「模板」最长不下降子序列 LIS

最长不下降子序列 LIS

在一个数字序列中，找到一个最长的子序列(可以不连续)，使得这个子序列是不下降(非递减)的。

例如，现有序列A = {1,2,3,-1,-2,7,9}（下标从1开始），它的最长不下降子序列是{1,2,3,7,9},长度为5。另外，还有一些子序列是不下降子序列，比如{1,2,3}，{-2,7,9}等，但都不是最长的。

输入

第一行为n，表示n个数 第二行n个数

输出

最长不下降子序列的长度

样例

样例输入1

3
1 2 3

样例输出1

3

提示

N小于5000,且每个数\(\le max int\)

Code

dp

#include <bits/stdc++.h>
using namespace std;
int a[5005],dp[5005];
int main()
{
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	for(int i=1;i<=n;i++)
	{
		dp[i]=1;//一开始就置为1
		for(int j=1;j<i;j++)
		{
			if(a[j]<=a[i])
			{//所有可能更新dp[i]的j
				if(dp[i]<=dp[j]+1)
				{
					dp[i]=dp[j]+1;
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(ans<dp[i])
		{
			ans=dp[i];
		}
	}
	cout << ans;
	return 0;
}