Skip to content

Sixian Li

Longest Increasing Subsequence And Patience Game(Part1)

Algorithm

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

Problem

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

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.

deck
Picture from Princeton slides

Patience

Rules

  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.

Observation1

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

Card

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

Proof

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,

IS

2 4 7 8 Q is an IS.

Let’s prove this.

Observation2

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

Proof

Deck

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.

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.

Pointer

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

Reference

Longest Increasing Subsequence

Patience Sorting