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      2017.09.20 23:43

fight_in_dl      2017.09.07 05:33

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

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 代码，有详细的注释，动态规划