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


  • 3
    Xenonn  commented on Nov. 27, 2020, 12:53 p.m.

    I think the problem type should be Dynamic Programming, no?


    • 1
      Evanhyd  commented on Feb. 25, 2021, 9:35 p.m.

      well, patience sort also works(in fact better), so it is not necessarily a DP problem.


    • -1
      c  commented on Nov. 27, 2020, 1:30 p.m.

      This problem was imported from WCIPEG, which doesn't have problem categories and we don't have the resources to manually categorize every problem.