Find the longest strictly rising run you can pick out of a list, skipping but never reordering. Build the answer for each ending number from the ones before it, then a bonus O(n log n) trick.
▼The problem
LeetCode 300 (Medium). Given a list of numbers, return the length of the longest strictly increasing subsequence (numbers may be skipped, not reordered).
Example (LeetCode's): [10, 9, 2, 5, 3, 7, 101, 18] → 4 (for example 2, 5, 7, 101).
The solution
def length_of_lis(nums):
dp = [1] * len(nums) # badges
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)Transcript
Longest Increasing Subsequence. Find the length of the longest subsequence of a list that strictly increases. You may skip numbers, but not reorder them.
Take ten, nine, two, five, three, seven, a hundred and one, eighteen. Two, five, seven, a hundred and one climbs four steps. The answer is four.
The naive way tries every subsequence: each number in or out, two to the n choices. Forty numbers means over a trillion.
Instead, give each pillar a badge: the longest increasing run ending right there. Look back at every earlier, lower pillar, take the best badge, and add one. Nothing lower? The badge is one.
In code, every badge starts at one. For each i, check every j before it. If nums j is smaller, badge i becomes the larger of itself and badge j plus one. Return the biggest badge.
Let's climb. Ten, nine and two have nothing lower behind them: one each. Five reaches back to two: two. Three also reaches two: two. Seven sees two, five and three; the best is two, so three. A hundred and one builds on seven: four. So does eighteen. Follow the links back: two, five, seven, a hundred and one.
Each pillar looks back at every earlier one, so the time is n squared, with n space.
Bonus: keep the smallest tail for each length, and binary search where each number goes. That's n log n.
Look back, take the best, add one. That's Longest Increasing Subsequence.