Longest Increasing Subsequence

Editorial

The Longest Increasing Subsequence (LIS) is a staple dynamic-programming interview problem: find the length of the longest strictly increasing subsequence, where elements need not be contiguous.

O(n²) dynamic programming

Let dp[i] be the LIS length ending at index i; for each i, take the best over every earlier j with nums[j] < nums[i].

O(n log n) patience sorting

Maintain tails, where tails[k] is the smallest possible tail of an increasing subsequence of length k+1. Binary-search each value's position; if it lands past the end, the LIS grew by one.

tails = []
for x in nums:
    i = bisect_left(tails, x)
    if i == len(tails): tails.append(x)
    else: tails[i] = x
return len(tails)

Complexity

Time: O(n log n). Space: O(n).