Longest Increasing Subsequence

Given 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.

For example:
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.

Input

N <= 5000, the number of integers.
N lines, each with a value in the array.

Output

The length of the longest increasing subsequence of the array.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 27, 2013

Problem Types: [Show] [Hide]

• Dynamic Programming

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)