Longest Increasing Subsequence

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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


  • 2
    andrewtam  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?


    • 2
      c  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.


  • -6
    Plasmatic  commented on Oct. 21, 2018, 11:39 p.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.