Implement longest increasing subsequence algorithm

[ajcr]

It would be interesting to try and implement an algorithm to find the longest increasing subsequence in a sliding window.

Such an approach is described in Albert et al., 2004:

• https://pdfs.semanticscholar.org/5517/cc2a743fa07f2ae2fa6442ca77a8b419a8ee.pdf

[ajcr]

Actually, there is another algorithm by Chen et al. that computes the value in O( output ) time:

• https://ac.els-cdn.com/S0304397507001235/1-s2.0-S0304397507001235-main.pdf?_tid=945b9a2a-034f-11e8-b8f0-00000aab0f6c&acdnat=1517050276_a53f458b7d7310f11436f72772056dfa

This is (theortically) an improvement on the O ( log log n + output ) approach in the paper above.

Also, the construction looks possibly easier to implement and more practical as it does not rely on Emde Boas trees.