信息学奥赛一本通——1281：最长上升子序列

---

题目

【题目描述】

一个数的序列$b_i$，当$b_1<b_2<...<b_S$的时候，我们称这个序列是上升的。对于给定的一个序列$(a_1,a_2,...,a_N)$，我们可以得到一些上升的子序列$(a_{i1},a_{i2},...,a_{iK})$，这里$1\le i_1<i_2<...<i_K\le N$。比如，对于序列$(1,7,3,5,9,4,8)$，有它的一些上升子序列，如$(1,7),(3,4,8)$等等。这些子序列中最长的长度是4，比如子序列$(1,3,5,8)$。

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

【输入】

输入的第一行是序列的长度$N(1\le N\le 1000)$。第二行给出序列中的N个整数，这些整数的取值范围都在$0$~$10000$。

【输出】

最长上升子序列的长度。

【输入样例】

7
1 7 3 5 9 4 8

【输出样例】

4

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,a[1145],f[1145],i,j,ans=1;
int main() {cin>>n;for(i=1;i<=n;i++) {cin>>a[i];}for(i=1;i<=n;i++) {f[i]=1;}for(i=1;i<=n;i++) {for(j=1;j<i;j++) {if(a[i]>a[j]) {f[i]=max(f[j]+1,f[i]);}}ans=max(ans,f[i]);}cout<<ans;return 0;
}