We maintain an array $$$E$$$, where $$$E_i$$$ is the smallest number that a LIS of length $$$i$$$ can $$$E$$$ nd with. At the start, $$$E_i = inf$$$ for all $$$1 \leq i \leq N$$$, and $$$E_0 = -inf$$$.

Then, process the numbers of the input array $$$A$$$ from left to right. Let's say we're on $$$A_k$$$. We want to find the last index $$$i$$$ in $$$E$$$ such that $$$E_i < A_k$$$. What this means is that, using the numbers $$$A_0, \cdots, A_{k-1}$$$, we could build a LIS of length $$$i$$$ which ends with $$$E_i$$$, a number smaller than $$$A_k$$$. We can then append $$$A_k$$$ to this LIS, getting a LIS of length $$$i+1$$$ ending with $$$A_k$$$. This means $$$E_{i+1} = min(E_{i+1},A_k)$$$.

This is the only improvement we can make, as we couldn't append $$$A_k$$$ to LIS's represented by $$$E_{i+1}, \cdots, E_N$$$ as their last elements are $$$ \geq A_k$$$, so they wouldn't be LIS after appending $$$A_k$$$, and there is no point appending $$$A_k$$$ to LIS's represented by $$$E_0, \cdots, E_{i-1}$$$ as we already have LIS's longer than them ending in a number smaller than $$$A_k$$$.

In each step, we have for every length $$$i$$$ the smallest number that a LIS of that length can end with, using the numbers we have processed so far. At the end, we have the answer for the whole array $$$A$$$: $$$E_L$$$. If it's $$$inf$$$, there is no LIS of length $$$L$$$ in $$$A$$$.

The step 'find the last index $$$i$$$ in $$$E$$$ such that $$$E_i < A_k$$$' can be done using binary search, as $$$E_i$$$ is non-decreasing. The complexity is $$$O(NlogN)$$$.