DP: longest increasing subsequence

A subsequence keeps the original order but may skip elements. We want the length of the longest subsequence whose values are strictly increasing.

For [10, 9, 2, 5, 3, 7, 101, 18] one longest increasing subsequence is [2, 3, 7, 18] (or [2, 3, 7, 101]) — length 4.

The classic dynamic-programming idea: let dp[i] be the length of the longest increasing subsequence that ends at index i. Any such subsequence either is just nums[i] alone, or extends an earlier one ending at some j < i whose value is smaller:

dp[i] = 1 + max((dp[j] for j in range(i) if nums[j] < nums[i]), default=0)

The answer is the largest value in dp (or 0 for an empty list).

Your task

Write length_of_lis(nums) returning the length of the longest strictly increasing subsequence of nums.

length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])  # 4
length_of_lis([0, 1, 0, 3, 2, 3])             # 4   -> [0, 1, 2, 3]
length_of_lis([7, 7, 7])                       # 1   -> equal values don't increase
length_of_lis([])                              # 0

Hint: build a dp list of all 1s (each element alone is a subsequence of length 1), then for each i look back at every smaller earlier value and take the best extension.