最长上升子序列模版

发布时间：2020-12-14 04:15:12 所属栏目：大数据来源：网络整理

导读：总时间限制:? 2000ms ? 内存限制:? 65536kB 描述一个数的序列 b i ，当 b 1 ?? b 2 ? ... ? b S 的时候，我们称这个序列是上升的。对于给定的一个序列( a 1 ,? a 2 ,...,? a N )，我们可以得到一些上升的子序列( a i 1 ,? a i 2 ,? a i K )，这里1 =? i 1 ?

总时间限制:?: 2000ms
内存限制:?: 65536kB

描述

一个数的序列b_i，当b₁?<?b₂?< ... <?b_S的时候，我们称这个序列是上升的。对于给定的一个序列(a₁,?a₂,...,?a_N)，我们可以得到一些上升的子序列(a_i₁,?a_i₂,?a_{i_K})，这里1 <=?i₁?<?i₂?< ... <?i_K?<= N。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,8)等等。这些子序列中最长的长度是4，比如子序列(1,8).

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

输入

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

输出

最长上升子序列的长度。

样例输入

7
1 7 3 5 9 4 8

样例输出

来源

翻译自 Northeastern Europe 2002,Far-Eastern Subregion 的比赛试题

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int i,j,n,a[1005],f[1005],ans;
 7 int main()
 8 {
 9     scanf("%d",&n);
10     for(i = 1;i <= n;i++)
11     {
12         scanf("%d",&a[i]); 
13     }
14     for(i = n - 1;i >= 1;i--)
15     {
16         for(j = n;j > i;j--)
17         {
18             if(a[j] > a[i])
19             f[i] = max(f[i],f[j] + 1);
20         }
21         ans = max(ans,f[i]);
22     }
23     printf("%d",ans + 1);
24     return 0;
25  }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!