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
hide comments
|
for_sx_e_1:
2021-04-20 10:53:35
I think NlogN isn't a good choice. |
|
lotus_guy:
2015-03-05 14:24:12
nice Last edit: 2017-04-11 11:37:42 |
|
José Carlos Gutiérrez:
2015-02-24 22:22:19
my O(N*log^2 N) solution got AC |
|
crccw:
2014-08-23 22:30:02
7
|
|
つ ◕_◕ ༽つ GIFF AC:
2014-08-12 10:37:34
@Diptesh I believe subsequence in this problem means subsegment |
|
Diptesh Patel:
2014-07-26 18:51:04
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. |
|
Hasan Jaddouh:
2013-06-11 13:33:50
my solution completely wrong ,but got AC |
|
Ортур:
2012-07-10 08:48:03
I got AC with nlogn without any optimisations. |
|
haoyifan:
2012-03-22 01:26:57
thx,but,
|
|
Buda IM (retired):
2012-03-12 06:14:10
Be ware this problem has VERY tight TL. You can AC with NlogN with many constant optimisations. I think O(N) is expected. |
| 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 |
RSS