Longest Increasing Subsequence and Patience Game(Part1)

Idea behind the O(nlogn) solution

This part focuses on the idea behind the solution. The actual implementation will be covered in Part2.


Given an unsorted array of integers, find the length of longest increasing subsequence. Example from LeetCode:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

The O(n2)O(n^2) dynamic programming solution is quite straightforward. But I’m surprised to see the relationship between the card game Patience and LIS.


Princeton slides



  1. You can only place a lowered-valued(or equal-valued) card on top of a higher-valued card, e.g., 2 on top of 3. Note Ace is NOT 1 here.

  2. You can form a new pile and put your card onto it.

To understand why it’s related to LIS, we need to make two observations.


For any legal strategy, #piles\#\text{piles} \geq length of any increasing subsequence


Claim: Any increasing subsequence can use at most one card from each pile.


Assume we used yy and yy' from this pile. Since yy is on top of yy', yyy \le y’.

If y=yy = y’, they can’t form an increasing sequence. “increasing” is different from “non-decreasing”.

If y<yy \lt y’, the only way to use both cards in an increasing sequence is to place yy' after yy in that sequence. But yy is on top of yy', so yy' comes before yy in the original array.

For example, [y', y] = [5, 2], 5 -> 2 is not an IS.

Thus, you can’t form an IS with more than one card from a pile \Rightarrow length of any IS is at most #piles\#\text{piles}.

Greedy algorithm

Idea: put the new card on the leftmost pile possible, i.e., the first pile from left to right, such that new cardtop card of the pile\text{new card} \le \text{top card of the pile}.

If we play the game with this strategy, we will notice that top cards form an IS(increasing sequence). For example,


2 4 7 8 Q is an IS.

Let’s prove this.


Using the greedy strategy, top cards of piles increase from left to right at any time of the game



Assume x<yx \lt y, so we don’t have an IS. We have two cases:

  1. yy comes before xx

    Then xx must be placed on top of yy by the algorithm. Contradiction.

  2. yy comes after xx

    Since xx is put into the red pile, x>yx \gt y' or it’ll be in the blue pile by our greedy algorithm. yy is on top of yy', so yyy \le y'. But we assumed x<yx \lt y, so x<yyx \lt y \le y' which contradicts x>yx\gt y'.

With these two observations, we can go head and prove the duality.


Lenght of LIS = #piles using the greedy strategy

Let the length of LIS be LL, and PP be the #piles\#\text{piles} created by the greedy algorithm. For an inequality, we have to show “\geq” and “\leq” directions.

  1. LPL \leq P

This follows directly from #piles\#\text{piles}\geq length of nay IS in observation 1. LIS is an IS, so LPL \leq P.

  1. LPL \geq P

From observation 2, we know top cards of piles increase from left to right at any time of the game using this algorithm.

Note that the top cards are in general not an increasing subsequence — Berkeley notes

In this case, the top cards are 2 4 7 8 Q, but 4 comes after 7 in the original deck, so 4 -> 7 is not an IS.


To keep track of a valid IS, at the time of insertion of a card cc, we keep a pointer from cc to the current top card to the left of cc. For example, when 5 is inserted, 3 is the top card on its left, so there’s an arrow from 5 to 3.

Assume P>LP \gt L, let the top card on the ithi\text{th} pile be aia_i. Since we have PP piles, we can follow the pointers starting at apa_p to get a1ap1apa_1\leftarrow…\leftarrow a_{p-1} \leftarrow a_p. Note that from left to right, a1<a2<<apa_1 \lt a_2 \lt \cdots \lt a_p. Thus, we get an IS of length PP.

But we claimed the length of the longest IS is LL. P>LP \gt L contraditcts that, so PL P \leq L \ \square


Longest Increasing Subsequence

Patience Sorting

欢迎通过 Twitter 邮件告诉我你的想法
Find me on Twitter or write me an email