# Patience Sorting for LIS

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

```id="p4h8x1"
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.