Patience sorting is a greedy sort that solves LIS in time . It goes as follows (from princeton.edu):

My implementation is in git and below:

Here’s another way to solve the longest increasing subsequence problem: Patience sorting (Wikipedia).

Patience sorting is a greedy sort that solves LIS in time . It goes as follows (from princeton.edu):

My implementation is in git and below: