Practice: Longest Increasing Subsequence
DP over endings.
In the list ten, nine, two, five, three, seven, one hundred and one, eighteen, what's the longest run of numbers that keeps going up, if you're allowed to skip numbers? Pause. What smaller question would help?

- Numbers that keep going up
- You may skip numbers
- How long can it be?
Best run ending here
Let best of I be the length of the longest increasing run that ends at position I. To compute it, look at every earlier number that's smaller, and extend its best run by one. The answer is the largest value in best. Run it. Four, for example two, three, seven, eighteen.
def lis(nums):
best = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
best[i] = max(best[i], best[j] + 1)
return max(best), best
length, best = lis([10, 9, 2, 5, 3, 7, 101, 18])
print("best:", best)
print("length:", length)best: [1, 1, 1, 2, 2, 3, 4, 4] length: 4
Faster versions
This version is O of N squared, which is fine for a few thousand numbers. There's a clever O of N log N version, which keeps the smallest possible tail for each length, and uses binary search to update it. But in an interview, the clear dynamic programming version is a great start.
| key | value |
|---|---|
| best[i] | longest run ending at i |
| Rule | extend smaller earlier runs |
| Cost | O(n²) |
| Faster | O(n log n) with bisect |
Summary
For the longest increasing subsequence, compute the best run ending at each position. Next, generating every valid set of brackets.
Key takeaways- best[i] ends at i
- Extend smaller ones
- Take the max