1576 最长严格上升子序列

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 黄金 Gold

题目描述 Description

给一个数组a1, a2 ... an，找到最长的上升降子序列ab1<ab2< .. <abk，其中b1<b2<..bk。

输出长度即可。

输入描述 Input Description

第一行，一个整数N。

第二行，N个整数（N < = 5000）

输出描述 Output Description

输出K的极大值，即最长不下降子序列的长度

样例输入 Sample Input

9 3 6 2 7

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【样例解释】

最长不下降子序列为3,6,7

 1 #include<iostream>
 2 using namespace std;
 3 int f[1001];
 4 int num[1001];
 5 int n,h,d; 
 6 int main() 
 7 {
 8     cin>>n;
 9     for(int i=1;i<=n;++i)
10         cin>>num[i];
11     for(int i=1;i<=n;++i)
12     {
13         f[i]=1;
14         for(int j=1;j<i;++j)
15         {
16             if(num[j]<num[i]) 
17             {
18                 f[i]=max(f[j]+1,f[i]);
19             }
20         }
21         d=max(d,f[i]);
22     }
23     cout<<d<<endl;
24     return 0;
25 }