POJ2533 Longest ordered subsequence
2024-10-13 01:00:50
Longest Ordered Subsequence
Description A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK<= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence. Input The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000
Output Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.
Sample Input 7 Sample Output 4 Source Northeastern Europe 2002, Far-Eastern Subregion
|
[Submit] [Go Back] [Status] [Discuss]
#include<cstdio>
#include<iostream>
using namespace std; int main()
{
int n, a[], cn = , Maxlenth[], M = ;
cin >> n;
for(int i = ; i < n; i++) {
cin >> a[i];
Maxlenth[i] = ;
}
for(int i = n - ; i >= ; i--) {
for(int j = i + ; j < n; j++) {
if(a[i] < a[j] && Maxlenth[i] <= Maxlenth[j]) Maxlenth[i] = + Maxlenth[j];
if(Maxlenth[i] > M) M = Maxlenth[i];
}
}
cout << M << endl;
return ;
}
最新文章
- 机顶盒上gridview+ScrollView的使用。
- fopen()和fclose()的用法
- POJ 3352-Road Construction (图论-双边联通分支算法)
- JQuery判断checkbox是否选中-批量
- gitignre
- Master Nginx(4) - Nginx as a Reverse Proxy
- OpenStack简单测试性能监控数据记录
- 使用Ratpack与Spring Boot构建高性能JVM微服务
- cmake让add_subdirectory()的所有target生成到同一目录
- Python常用模块-时间模块
- ensp 单臂路由实验
- C#轻量级通通讯组件StriveEngine —— C/S通信开源demo(2) —— 使用二进制协议 (附源码)
- .NET Garbage Collection配置在.net core的写法
- 活字格 QQ 群和客户
- 题解——P1133 教主的花园DP
- Mybatis学习链接
- Nodejs的测试和测试驱动开发
- HDU 1711 - Number Sequence - [KMP模板题]
- MySQL知识总结(二)基本语句总结
- ORACLE中查询被锁定的表,以及如何解锁