【題目描述】

一個(gè)數(shù)的序列bi，當(dāng)b1<b2<...<bS的時(shí)候，我們稱這個(gè)序列是上升的。對(duì)于給定的一個(gè)序列(a1,a2,...,aN)，我們可以得到一些上升的子序列(ai1,ai2,...,aiK)，這里1≤i1<i2<...<iK≤N。比如，對(duì)于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。這些子序列中最長(zhǎng)的長(zhǎng)度是4，比如子序列(1,3,5,8)。

你的任務(wù)，就是對(duì)于給定的序列，求出最長(zhǎng)上升子序列的長(zhǎng)度。

【輸入】

輸入的第一行是序列的長(zhǎng)度N(1≤N≤1000)。第二行給出序列中的N個(gè)整數(shù)，這些整數(shù)的取值范圍都在0到10000。

【輸出】

最長(zhǎng)上升子序列的長(zhǎng)度。

【輸入樣例】

7
1 7 3 5 9 4 8

【輸出樣例】

4

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 2520 #define E 1e-12 using namespace std; int a[N],f[N]; int main() {int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int maxx=-INF;for(int i=1;i<=n;i++){f[i]=1;for(int j=1;j<i;j++)if(a[j]<a[i]&&f[j]+1>f[i])f[i]=f[j]+1;maxx=max(maxx,f[i]);}cout<<maxx<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的最长上升子序列（信息学奥赛一本通-T1281）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。