Longest Increasing Subsequence

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 64M
PyPy 3 128M
Python 3 128M
Author:
alextxu
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


  • 0
    thunder200911133  commented on Oct. 22, 2024, 5:16 p.m.

    Think about a way to just get the length instead of the correct LIS sequence.


  • 0
    PhoenixCoolIce  commented on April 15, 2024, 11:25 p.m.

    Why does the 10p give more memory than the exact same thing, the 7p? here Is it not the same, or am I dumb?


    • 4
      BalintR  commented on April 16, 2024, 1:28 a.m.

      The problem you linked has N \le 5\,000 while this problem has N \le 1\,000\,000.


  • 0
    amolven16  commented on Sept. 1, 2021, 2:50 p.m.

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


    • 13
      dxke02  commented on Sept. 1, 2021, 3:16 p.m. ← edit 2

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

      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 \mathcal{O}(N^2), and when N is as large as 10^6 you are using around 10^{12} operations.
      Assuming DMOJ can execute 10^8 operations a second, you would need around 10000 seconds, or like 3 hours of computation time.
      (probably more since you're using python...)
      Try to solve this problem in \mathcal{O}(N \log N) time.

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


      • 2
        DM__Oscar  commented on Sept. 1, 2021, 11:20 p.m.

        im so proud of you tony :)


  • 3
    andrewtam  commented on Sept. 29, 2020, 7: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?


    • 7
      c  commented on Sept. 29, 2020, 11: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.


  • 1
    Plasmatic  commented on Oct. 22, 2018, 3:39 a.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