This is a truly classic problem. The opener in one of the big algorithms textbooks on dynamic programming, I’m glad it’s included in the dynamic programming study plan. I bet there is an even prettier way of writing this code, but here is the solution I have:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        T = [1] # the first thing is always a sequence
        for i in range(1, len(nums)):
            best = 1
            for j in range(i):
                if nums[j] < nums[i]:
                    best = max(best, T[j]+1)
            T.append(best)
        return max(T)

Recurrence

T[i] is the length of the longest increasing subsequence that has to include the i’th element in nums. Compare to the recurrence in the previous question we discussed; there are similarities, but the big difference here is that our solution at i can build off of any previous solution that ends with a value smaller than ours, versus our solution having to be just contiguous with the previous solution.

So in more depth:

1. T[i] is the length of the longest increasing subsequence of nums[:i+1] that include nums[i]. Taking the max of this array will find the solution.
2. T[i] is computed via that append call, so we append the best value. We consider all values in T[:i] — recall T[j] is the length of the longest subsequence ending with nums[j]. If nums[j] < nums[i], we can “continue” that subsequence with nums[i], and so increase its length by 1.
3. Through the “magic of recursion”, we are able to kick-start this process by defining T up to T[:1], i.e., T = [1].

The Dasgupta algorithm book explains this in a very graph-theoretic way, which I appreciate but is also kind of a lot.

See here for more dynamic programming problems and solution.