AcWing 895. 最长上升子序列
原题链接
简单
作者:
永远热爱
,
2021-08-20 15:20:36
,
所有人可见
,
阅读 276
#include<iostream>
using namespace std;
const int N = 1100;
int a[N];
int dp[N];
// dp[i] 的含义是以i结尾的最长上升的子序列
// 初始化的话是 每一个dp[i] = 1 因为每一个数字是算单独的一个嘛
// 关系是 f[i] = (1 <= j < i) (f[i],f[j] + 1); 条件是 if(a[j] < a[i] ) 因为(j<i) 只有 a[j] < a[i] 才算上升序列
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;
for(int j=1;j<i;j++)
{
if(a[j] < a[i])
dp[i] = max(dp[i],dp[j] + 1);
}
}
int res = 0;
for(int i=1;i<=n;i++)
res = max(res,dp[i]);
cout << res << '\n';
return 0;
}