Longest Increasing Subsequence

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Given an array of integers, find and output the length of the longest increasing subsequence.

Input Specification

Line 1: N, the length of the array.

Line 2: An array A containing N integers, with each element separated by a single space.

Output Specification

The only line of output should contain the length of the longest increasing subsequence.

Constraints

1 \le N \le 1 000 000

0 \le A_i < 10^9

Sample Input 1

5
1 5 2 6 4

Sample Output 1

3

Sample Input 2

5
1 2 2 2 2

Sample Output 2

2

Comments


  • -5
    Plasmatic  commented on Oct. 21, 2018, 11:39 p.m. edited

    If only memory limit was larger... then you can AC using a segment tree

    Edit: xiaowuc1 AC'd using a segment tree so I guess I'm just dumb