AI Hints
Home›DSA in Python Tutorial›More Practice: Heaps, Search and DP
DSA in Python · Lesson 120 of 132

Practice: Longest Increasing Subsequence

DP over endings.

⏱ 2 min read▶ Video at 2:23:07🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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?

Practice: Longest Increasing Subsequence
From the video: Practice: Longest Increasing Subsequence
  • 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.

lis.pypython
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)
Output
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.

keyvalue
best[i]longest run ending at i
Ruleextend smaller earlier runs
CostO(n²)
FasterO(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
Next up: Practice: Generate Parentheses — backtracking with rules