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
Why does the 10p give more memory than the exact same thing, the 7p? here Is it not the same, or am I dumb?
The problem you linked has while this problem has .
Oh I'm dumb lmao
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