LIS–最长不下降子序列
输入
8
1 2 3 -9 3 9 0 11
输出
6
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100;
int A[N],dp[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
}
//记录最大的dp[i]
int ans=-1;
for(int i=1;i<=n;i++)
{
//边界初始条件
dp[i]=1;
for(int j=1;j<i;j++)
{
if(A[i] >= A[j] && ( dp[j]+1 >dp[i] ) )
{
dp[i]=dp[j]+1;
}
}
ans=max(ans,dp[i]);
}
printf("%d",ans);
return 0;
}