Longest Increasing SubsequenceGiven an array of integers, find the longest increasing subsequence.
A subsequence is just a collection of numbers from the array - however, they must be in order.
Array: 1 2 5 4 3 6
The longest increasing subsequence here is 1 2 5 6 (or 1 2 4 6, or 1 2 3 6).
The numbers must be strictly increasing - no two numbers can be equal.
InputN <= 5000, the number of integers.
N lines, each with a value in the array.
OutputThe length of the longest increasing subsequence of the array.
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 27, 2013
- Dynamic Programming
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3