AcWing 895. 最长上升子序列
原题链接
简单
作者:
未名湖畔的梦
,
2021-02-13 20:41:30
,
所有人可见
,
阅读 310
#include <cstdio>
#include <algorithm>
#define MAXN 1005
using namespace std;
// f[x] 表示以 a[x] 结尾的序列的最大长度
// 想要得到 f[x] 就要得到 f[x]前面一个子序列的最大长度
// 即f[p] (f[p] 表示以 a[p] 结尾的序列 )
// 明显有: a[p] < a[x] && p < x
// 即 p 在 x 前面(p的位置在x前面) 并且 a[p] < a[x](递增的序列)
int f[MAXN] , n , a[MAXN] , ans ;
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d",a+i);
for(int i = 1; i <= n; i++){
f[i] = 1;
for(int p = 0; p < i; p++){
if(a[p] < a[i])
f[i] = max(f[i],f[p]+1) ;
ans = max(ans, f[i]);
}
}
printf("%d",ans);
return 0;
}