Given a sequence $A$, its LIS (Longest Increasing Sequence) can be found as follows.

Apply coordinate compression to assume $1 \leq A_i \leq N$. We adopt Dynamic Programming (DP). Let $\mathrm{dp}[i][j]$ be the length of a LIS, chosen from the first $i$ elements, and whose last element is $j$. The initial states are $\mathrm{dp}[0][0] = 0$ and $\mathrm{dp}[0][1] = \mathrm{dp}[0][2] = \dots = \mathrm{dp}[0][N] = \mathrm{-inf} $, and the transitions for $i = 1, 2, \dots ,N$ are as follows:

• $\displaystyle \mathrm{dp}[i][j] = \max_{0 \leq k < j} \mathrm{dp}[i - 1][k] + 1$ for $j = A_i$.
• $\displaystyle \mathrm{dp}[i][j] = \mathrm{dp}[i - 1][j]$ for $j \neq A_i$.

The complexity of a naive implementation would cost $O(N^2)$, but it can be reduced to $O(N \log N)$. There are mainly two approaches. We introduce a way that uses a segment tree.

The DP above can be simply represented as pseudocode as follows:

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

With a segment tree with segment-max retrieval, the DP above can be turned into in-place style:

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

The segment-max retrieval of a segment tree costs $O(\log N)$ time, so the length of a LIS can be obtained in $O(N \log N)$ time. An auxiliary array enables us to reconstruct a LIS too.