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):


My implementation is in git and below:

Leave a Reply

Your email address will not be published. Required fields are marked *