与えられた列 $A$ に対して、　 LIS (最長増加部分列) は以下のようにして求められます。

$A$ を座標圧縮して $1 \leq A_i \leq N$ を仮定します。動的計画法を用います。$\mathrm{dp}[i][j]$ を $A$ の $i$ 番目までの要素を考えて最後に用いた要素の値が $j$ である LIS の長さと定義します。初期状態は $\mathrm{dp}[0][0] = 0, \mathrm{dp}[0][1] = \mathrm{dp}[0][2] = \dots = \mathrm{dp}[0][N] = \mathrm{-inf} $ とし、遷移は、 $i = 1, 2, \dots ,N$ について順に、

• $j = A_i$ について $\displaystyle \mathrm{dp}[i][j] = \max_{0 \leq k < j} \mathrm{dp}[i - 1][k] + 1$
• $j \neq A_i$ について $\displaystyle \mathrm{dp}[i][j] = \mathrm{dp}[i - 1][j]$

愚直に実装すると計算量 $O(N^2)$ ですが、 $O(N \log N)$ にできます。大きく二つの方法があると思いますが、 Segment Tree を用いる方法を紹介します。

先程の DP を疑似コードにすると、非常に単純になります:

dp = [N + 1] * [N + 1]
dp.fill(-inf)
dp[0][0] = 0
for (int i : (1, N))
    max_value = 0
    for (int j : (0, A[i] - 1))
        max_value = max(max_value, dp[i - 1][j])
    dp[i][j] = max_value + 1

DP を in-place 化すると、区間の最大値を求められる Segment Tree を用いてこれは以下のように書けます。

RangeMaxSegmentTree dp(N + 1, -inf)
dp[0] = 0
for (int i : (1, N))
    dp[a[i]] = dp.calc_max(0, A[i] - 1) + 1

Segment Tree での区間 max は $O(\log N)$ の計算量なので、 LIS の長さが $O(N \log N)$ で求められることになります。補助的な配列を用いれば LIS を復元することもできます。