Submit solution

Points:
10

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.

#### Constraints

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

Can someone help me? Even if I a, using an optimized DP approach, I am getting either a TLE or an MLE (Python).

Your claims about an "optimized DP approach" are wrong.

Your time complexity is , and when is as large as you are using around operations.

Assuming DMOJ can execute operations a second, you would need around seconds, or like hours of computation time.

(probably more since you're using python...)

Try to solve this problem in time.

Also for future reference, please consult the DMOJ discord server.

im so proud of you tony :)

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?

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

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