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]

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

Comments (Search)

I'm getting all of them wrong. Please help.

Please research on dynamic programming, just like golf, you have failed to utilize dynamic programming, as a note, i gave you some hints for golf, please check that out,then understand dynamic programming, which should help you greatly for questions that require the use of dynamic programming