6. Longest Increasing Subsequence
MediumDynamic ProgrammingBinary Search
Print the length of the longest strictly increasing subsequence of the array (elements need not be contiguous).
Input format
Line 1: n Line 2: n integers
Output format
The length of the LIS.
Example 1
Input
8 10 9 2 5 3 7 101 18
Output
4
Explanation: One LIS is [2, 3, 7, 101].
Example 2
Input
6 0 1 0 3 2 3
Output
4
Explanation: One LIS is [0, 1, 2, 3].
Constraints
1 ≤ n ≤ 2500
Read input from standard input and print the answer to standard output. Your code is judged against 6 test cases, most of them hidden.
Loading the MyLoginn IDE…