普通 DP 解法： 定义 $dp[i]$ 表示以第 i 个元素结尾的最长上升子序列长度。

初始化 $dp[i] = 1$。

若存在 $j < i$ 且 $a_j < a_i$，则有：$dp[i] = max(dp[i], dp[j] + 1)$。

答案即为 $max(dp[i])$。

但此算法为 $O(2^n)$，在 $n = 1000000$ 时会超时。

贪心 + 二分优化： 维护一个数组 $tail$，其中 $tail[k]$ 表示长度为 $k+1$ 的上升子序列的最小结尾值。

对于每个高度 $x$：

若 $x > tail[−1]$，说明可以延长子序列，将 $x$ 追加；

否则用二分查找第一个 $≥x$ 的位置，用 $x$ 替换该值。

最后 $tail$ 的长度即为 $LIS$ 长度。

这种方法并不真正记录序列，但可保证长度最优。

时间复杂度：$O(n)$