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:
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(n^2)$ dynamic programming solution is quite straightforward. But I’m surprised to see the relationship between the card game Patience and LIS.
Patience
Rules

You can only place a loweredvalued(or equalvalued) card on top of a highervalued card, e.g.,
2
on top of3
. Note Ace is NOT1
here. 
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, $\#\text{piles}$ $\geq$ length of any increasing subsequence
Claim: Any increasing subsequence can use at most one card from each pile.
Proof
Assume we used $y$ and $y'$ from this pile. Since $y$ is on top of $y'$, $y \le y’$.
If $y = y’$, they can’t form an increasing sequence. “increasing” is different from “nondecreasing”.
If $y \lt y’$, the only way to use both cards in an increasing sequence is to place $y'$ after $y$ in that sequence. But $y$ is on top of $y'$, so $y'$ comes before $y$ 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 $\#\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 $\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.
Observation2
Using the greedy strategy, top cards of piles increase from left to right at any time of the game
Proof
Assume $x \lt y$, so we don’t have an IS. We have two cases:

$y$ comes before $x$
Then $x$ must be placed on top of $y$ by the algorithm. Contradiction.

$y$ comes after $x$
Since $x$ is put into the red pile, $x \gt y'$ or it’ll be in the blue pile by our greedy algorithm. $y$ is on top of $y'$, so $y \le y'$. But we assumed $x \lt y$, so $x \lt y \le y'$ which contradicts $x\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 $L$, and $P$ be the $\#\text{piles}$ created by the greedy algorithm. For an inequality, we have to show $“\geq”$ and $“\leq”$ directions.
 $L \leq P$
This follows directly from $\#\text{piles}\geq$ length of nay IS in observation 1. LIS is an IS, so $L \leq P$.
 $L \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 $c$, we keep a pointer from $c$ to the current top card to the left of $c$. 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 \gt L$, let the top card on the $i\text{th}$ pile be $a_i$. Since we have $P$ piles, we can follow the pointers starting at $a_p$ to get $a_1\leftarrow…\leftarrow a_{p1} \leftarrow a_p$. Note that from left to right, $a_1 \lt a_2 \lt \cdots \lt a_p$. Thus, we get an IS of length $P$.
But we claimed the length of the longest IS is $L$. $P \gt L$ contraditcts that, so $P \leq L \ \square$