Chef and Numbers
All submissions for this problem are available.
Read problems statements in Russian also.
Chef plays with the sequence of N numbers. During a single move Chef is able to choose a non-decreasing subsequence of the sequence and to remove it from the sequence. Help him to remove all the numbers in the minimal number of moves.
The first line of each test case contains a single N denoting the number of integers in the given sequence. The second line contains N space-separated integers A1, A2, ..., AN denoting the given sequence
Output a single line containing the minimal number of moves required to remove all the numbers from the sequence.
- 1 ≤ N ≤ 100000.
- 1 ≤ Ai ≤ 100000.
Input: 3 1 2 3 Output: 1
Input: 4 4 1 2 3 Output: 2
Subtask 1 (10 points): N = 10
Subtask 2 (40 points): N = 2000
Subtask 2 (50 points): N = 100000
|Tags||dynamic-programming, easy, furko, ltime08|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.