Medium Tabulation Dynamic Programming
In plain English: Find the longest chain of numbers in an array that are strictly increasing (not necessarily adjacent).
For each element, check all previous elements — if a[j] < a[i], then dp[i] = max(dp[i], dp[j]+1). The O(n log n) approach uses patience sorting.
Prompt
Given an array of integers, find the length of the longest strictly increasing subsequence.
Try to write it from scratch before scrolling down.
Solution
import bisect
def length_of_lis(nums):
# O(n log n) using patience sorting
tails = []
for x in nums:
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
tails.append(x) # extend longest subsequence
else:
tails[pos] = x # replace to keep smallest tail
return len(tails)
# Test: length_of_lis([10,9,2,5,3,7,101,18]) == 4 (2,3,7,101)
# Test: length_of_lis([0,1,0,3,2,3]) == 4