与えられた列 $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 を復元することもできます。

答えが $L + 1$ になるとします。編集した後の $A$ の長さ $L + 1$ の狭義単調増加部分列は、編集する前の $A$ の LIS と編集した要素からなる必要があります。 逆に、 $A$ の全ての LIS について、その LIS と編集した要素からなる長さ $L + 1$ の狭義単調増加部分列が作れるかどうかが上の制限に影響されないことを示せばよいです。

長さ $L$ の LIS の "すき間" の要素をうまく編集して、長さ $L + 1$ の狭義単調増加部分列を作ることを考えます。このとき操作に上の制限を設けても問題ないことは、 (厳密に証明すると長くなりますが) 簡単にわかります。