Longest increasing subsequence 2 - MarisaOJ: Marisa Online Judge

Longest increasing subsequence 2

Time limit: 1000 ms
Memory limit: 256 MB
You are given an array $A$ of $n$ integers, find the longest increasing subsequence (LIS) of $A$. In other words, find the largest $k$ that there exist $k$ indices $i_1 < i_2 < ... < i_k$ that $A_{i_1} < A_{i_2} < ... < A_{i_k}$. ### Input - The first line contains an integer $n$. - The second line contains $n$ integer $A_i$. ### Output - Print the length of the LIS. ### Constraints - $1 \le n \le 10^5$ - $1 \le A_i \le 10^9$. ### Example Input: ``` 5 3 7 2 1 8 ``` Output: ``` 3 ``` #### Note: The LIS is $(3, 7, 8)$.