Dynamic ProgrammingBinary SearchArray
Find the length of the longest strictly increasing subsequence of an array. A subsequence keeps the original order but may skip elements.
Input
Line 1: n. Line 2: n integers.
Output
Print the length of the longest strictly increasing subsequence.
Constraints
1 <= n <= 2 * 10^4 -10^4 <= each value <= 10^4
Example 1
Input
8 10 9 2 5 3 7 101 18
Output
4
One LIS is 2 3 7 18 (length 4).