LIS in O(n log n)

The Idea

The O(n²) version asks every element which earlier one it can extend. The faster version keeps one array: the smallest value that can end an increasing chain of each length. Each number either extends the array or replaces the first entry that is not smaller, found by binary search. Length comes out right; the array itself is not the subsequence.

Real-World Example

A card game where each card goes on the first pile whose top card is not lower, or starts a new pile. The number of piles is the answer, and the piles keep their tops as low as possible so later cards still have somewhere to land.

The Code

from bisect import bisect_left

nums = [10, 9, 2, 5, 3, 7, 101, 18]
tails = []
for n in nums:
    i = bisect_left(tails, n)    # first tail that is not smaller than n
    if i == len(tails):
        tails.append(n)          # n extends the longest chain so far
    else:
        tails[i] = n             # same length, smaller ending

print(tails)        # [2, 3, 7, 18] — a length, not the actual subsequence
print(len(tails))   # 4

from bisect import bisect_left
tails = []
for n in [4, 5, 1, 2, 3]:
  i = bisect_left(tails, n)
  if i == len(tails):
      tails.append(n)
  else:
      tails[i] = n
print(tails, len(tails))