## Longest Increasing Subsequence

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 64M
PyPy 3 128M
Python 3 128M

Author:
Problem type

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

#### Input Specification

Line 1: , the length of the array.

Line 2: An array containing 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.

#### 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

• commented on Nov. 27, 2020, 4:25 p.m.

Should this problem be worth more points, since this is worth 7 points?

• commented on Nov. 27, 2020, 10:31 p.m.

Used to be 12 points

• commented on Sept. 29, 2020, 3:42 p.m.

Why does this submission https://dmoj.ca/submission/3042942 compiled with Java 11 pass every test case but an identical submission https://dmoj.ca/submission/3042941 compiled with Java 8 fail? Is there something that I'm missing?

• commented on Sept. 29, 2020, 7:01 p.m. edit 2

Compact Strings were introduced in Java 9, so reading in the entire line (which is up to 10 million characters) takes much less memory.

• 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