## Longest Increasing Subsequence

View as PDF

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.

#### 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 Sept. 1, 2021, 10:50 a.m.

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

• commented on Sept. 1, 2021, 11:16 a.m. edit 2

for i in range(1, N):
for j in range(0, i):
if X[i] > X[j] and DP[i] < DP[j] + 1:
DP[i] = DP[j] + 1


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.

• commented on Sept. 1, 2021, 7:20 p.m.

im so proud of you tony :)

• 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