Longest Increasing Subsequence

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 16M

Problem type

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 Specification

N \le 5\,000, the number of integers.
N lines, each with a value in the array.

Output Specification

The length of the longest increasing subsequence of the array.


Comments

There are no comments at the moment.