#29. 最長遞增子序列

題目描述

給你一個長度為 $N$ 的整數序列 $a_1, a_2, \ldots, a_N$，求嚴格遞增子序列的最大長度。

子序列是從原序列刪去部分元素（可以不刪）、其餘元素保持原順序得到的序列。

輸入格式

第一行一個整數 $N$（$1 \le N \le 10^5$）。 第二行 $N$ 個以空白隔開的整數 $a_i$（$1 \le a_i \le 10^9$）。

輸出格式

一行一個整數：最長嚴格遞增子序列的長度。

提示：$O(N^2)$ 的動態規劃會超時，需要 $O(N \log N)$ 的做法（二分搜尋）。