In order to obtain a faster solution for the problem, we construct a different dynamic programming solution that runs in $O(n^2)$, and then later improve it to $O(n \log n)$.

We will use the dynamic programming array $d[0 \dots n]$.

This time $d[l]$ doesn'tcorresponds to the element $a[i]$ or toan prefix of the array.

This time $d[l]$ doesn'tcorrespond to the element $a[i]$ or toa prefix of the array.

$d[l]$ will be the smallest element at which an increasing subsequence of length $l$ ends.

Initially we assume $d[0] = -\infty$ and for all other lengths $d[l] = \infty$.