Patience Sorting for LIS

Patience sorting is a technique that simulates a card game to compute the longest increasing subsequence (LIS). It builds piles with specific ordering rules and uses binary search to maintain efficiency.

You use it when you need the LIS in ( O(n \log n) ) time.

Problem

Given a sequence ( A ) of length ( n ), find the longest strictly increasing subsequence:

[ A[i_1] < A[i_2] < \dots < A[i_k], \quad i_1 < i_2 < \dots < i_k ]

Return either:

the length ( k ), or
the subsequence itself

Idea

Maintain a list of pile tops:

Each pile is increasing from bottom to top
The top values are kept in sorted order
For each element, place it on the leftmost pile whose top is greater than or equal to it

This ensures minimal pile tops.

Algorithm (Length only)

lis_length(A):
    piles = []

    for x in A:
        i = lower_bound(piles, x)
        if i == length(piles):
            piles.append(x)
        else:
            piles[i] = x

    return length(piles)

Example

Input:

[ A = [10, 9, 2, 5, 3, 7, 101, 18] ]

Steps (pile tops):

step	x	piles
1	10	[10]
2	9	[9]
3	2	[2]
4	5	[2, 5]
5	3	[2, 3]
6	7	[2, 3, 7]
7	101	[2, 3, 7, 101]
8	18	[2, 3, 7, 18]

Result:

[ \text{LIS length} = 4 ]

Correctness

The invariant is:

( piles[i] ) stores the smallest possible ending value of an increasing subsequence of length ( i+1 )

Replacing a pile top with a smaller value improves future extension possibilities without reducing achievable length.

The number of piles equals the LIS length.

Complexity

operation	cost
each step	( O(\log n) )
total	( O(n \log n) )

Space:

[ O(n) ]

Recovering the Sequence

To reconstruct the actual LIS, maintain:

predecessor indices
positions of pile updates

This adds bookkeeping but keeps time complexity unchanged.

When to Use

Use patience sorting when:

you need LIS efficiently
input size is large
only length or sequence matters, not full sorting

It is a standard technique in dynamic programming optimization and sequence analysis.