Longest Increasing Subsequence: Patience Sort

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 O(n lgn). It goes as follows (from princeton.edu):

patience

My implementation is in git and below:

Leave a Reply