2 shunfurh shunfurh 于 2017.09.06 17:17 提问

Longest Ordered Subsequence

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, the 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 of this sequence 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 contains the length of sequence N (1 <= N <= 1000). The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces.

Output

Output must contain a single integer - the length of the longest ordered subsequence of the given sequence.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Sample Input

1

7
1 7 3 5 9 4 8

Sample Output

4

2个回答

caozhy
caozhy   Ds   Rxr 2017.09.20 23:43
已采纳
fight_in_dl
fight_in_dl   Ds   Rxr 2017.09.07 05:33
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
E - Longest Ordered Subsequence(动态规划)最长升成子序列问题
E - Longest Ordered Subsequence A numeric sequence of ai is ordered if a1 a2 aN. Let the subsequence of the given numeric seque
POJ2533:Longest Ordered Subsequence(LIS)
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. F
N - Longest Ordered Subsequence——POJ 最长递增子序列
N - Longest Ordered Subsequence Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submit Status Description A numeric sequence of ai is ordered if a1 a2 aN
动态规划【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 ex
Longest Ordered Subsequence
Longest Ordered Subsequence,算法分析与设计,C语言程序
POJ 2533 Longest Ordered Subsequence 二分查找(LIS nlogn算法)
Longest Ordered Subsequence 时间复杂度为O(nlogn)的二分查找计算最长上升子序列的算法: 定义c数组:c[i]记录长度为i的上升子序列的结尾的值,其结尾值越小,意味着其潜能越大,越有可能被后来的数接上,所以每一个数扫一遍,利用二分法寻找恰好比它小的c数组的i值,更新一遍c数组,最后输出c数组的最长长度 #include #include #include #i
POJ-2533 Longest Ordered Subsequence(二分)
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring>using namespace std;int num[1005], ans[1005]; int main(){ int n; while(scanf("%d", &n) == 1){ for(int i = 0; i
HOJ 10027 Longest Ordered Subsequence Extention
Longest Ordered Subsequence Extention Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB Total submit users: 776, Accepted users: 552 Problem 10027 : No special judgeme
Pku acm 第2533题 Longest Ordered Subsequence 代码,有详细的注释
Pku acm 第2533题 Longest Ordered Subsequence 代码,有详细的注释,动态规划
动态规划 (Dynamic Programming) 之 最长公共子序列(Longest Common Subsequence)
这个问题也是算法导论上提过的问题。注意这个问题是Subsequence不是Substring。substring的话就是子串,子串的要求的连续相等的字符序列,而subsequence不要求连续。比如说ABCD和ABD。他们的longest common subsequence就是ABD。而Longest common substring就是AB。这个问题和Edit Distance是同样的一类