Submit | All submissions | Best solutions | Back to list |
LPERMUT - Longest Permutation |
You are given a sequence A of n integer numbers (1<=Ai<=n). A subsequence of A has the form Au, Au+1 ... , Av (1<=u<=v<=n). We are interested in subsequences that are permutations of 1, 2, .., k (k is the length of the subsequence).
Your task is to find the longest subsequence of this type.
Input
- Line 1: n (1<=n<=100000)
- Line 2: n numbers A1, A2, ... ,An (1<=Ai<=n)
Output
A single integer that is the length of the longest permutation
Example
Input: 5 4 1 3 1 2 Output: 3
Added by: | Jimmy |
Date: | 2006-02-20 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS PERL6 VB.NET |
Resource: | A problem put forward by Mr Mircea Pasoi |
hide comments
|
|||||
2021-04-20 10:53:35
I think NlogN isn't a good choice. |
|||||
2015-03-05 14:24:12 lotus_guy
nice Last edit: 2017-04-11 11:37:42 |
|||||
2015-02-24 22:22:19 José Carlos Gutiérrez
my O(N*log^2 N) solution got AC |
|||||
2014-08-23 22:30:02 crccw
7 6 5 1 3 3 3 3 anwsers 6 and got AC, Please review your tests |
|||||
2014-08-12 10:37:34 つ ◕_◕ ༽つ GIFF AC
@Diptesh I believe subsequence in this problem means subsegment |
|||||
2014-07-26 18:51:04 Diptesh Patel
Answer for the given test should be 4, As we need to find sub-sequence. The longest permutation from the sub-sequence is 4_312. |
|||||
2013-06-11 13:33:50 Hasan Jaddouh
my solution completely wrong ,but got AC |
|||||
2012-07-10 08:48:03 Ортур
I got AC with nlogn without any optimisations. |
|||||
2012-03-22 01:26:57 haoyifan
thx,but, 4 1 4 2 4 Why the answer is 2? |
|||||
2012-03-12 06:14:10 Buda IM (retired)
Be ware this problem has VERY tight TL. You can AC with NlogN with many constant optimisations. I think O(N) is expected. |