ZERO / HERO
Building the most patient stacks

Longest Increasing Subsequence

The analogy

Deal cards into piles: each card goes on the leftmost pile whose top is bigger than it, otherwise it starts a new pile. The number of piles at the end is the length of the longest increasing run you could have picked. Patience sorting, and it is far faster than checking every pair.

Visualizer

Patience piles

step 1 / 13
5
0
3
1
8
2
1
3
9
4
2
5
7
6
4
7

Longest increasing subsequence of [5, 3, 8, 1, 9, 2, 7, 4]. The O(n²) DP compares every pair; there is an O(n log n) way that feels like a card game.patience sorting

from bisect import bisect_left

def lis_length(a):
    tails = []
    for v in a:
        i = bisect_left(tails, v)      # strictly increasing
        if i == len(tails):
            tails.append(v)            # extends the LIS
        else:
            tails[i] = v               # tighter tail
    return len(tails)

# tails is sorted, so binary search is valid.
# tails is NOT the LIS itself — only its LENGTH is right.

def lis_dp(a):                         # O(n^2), gives the path
    n = len(a)
    dp, prev = [1] * n, [-1] * n
    for i in range(n):
        for j in range(i):
            if a[j] < a[i] and dp[j] + 1 > dp[i]:
                dp[i], prev[i] = dp[j] + 1, j
    return max(dp)
Check yourself

After the O(n log n) algorithm finishes, what is the tails array?