Longest Increasing Subsequence

This is a classic Dynamic Programming problem on Leetcode. The problem statement is simple: find the longest increasing subsequence in an array and return the length of said sequence. Usually keywords like "longest" or "max"Or conversely "shortest" or "min" are a strong signal for a dynamic programming solution. To have a proper plan for implementing this, a decision must be made on the state we are to be tracking in our dp array. Simply, dp[i] will track the longest subsequence that can be made at the ith index. So, we'll need to iterate thru the input array and... do what?

This is the part I stumbled on during implementation. Usually, you can just look for a one-pass solution and call it quits but its not that simple here. Since we are looking for a subsequence, ordering is not guaranteed. The implication of this is that the ith number might only be larger than the first number in the array. If i > 1, then how can our algorithm go back and find this? Well, the answer is not very satisfying, as a naive (and working) solution just backtracks through the entire array and finds the largest subsequence that it can add on to (the tail value is smaller than the current value). The solution looks like this:

n = len(nums)
dp = [1] * n
for i in range(1,n):
	longestSub = 0
	for j in range(i-1, -1, -1):
		if nums[j] < nums[i]:
			longestSub = max(longestSub, dp[j])
	dp[i] = 1 + longestSub
return max(dp)

What you see here is exactly what is described above. For every index in the input array, you look back through all previous indices, find the longest valid substring, and then store it in the current state. This is $O(n^2)$ runtime and $O(n)$ space. The best solution maintains these core ideas but implements it with more finesse. The key to the above implementation is that you need to search through every previous element to find the best subsequence, but what if instead you maintained a list of values greedily added that would speedup the process? To see this, look at an example input array: [1,3,2...]. Try to think of any reason that you would ever need to see the value 3 again for the rest of this process. The answer, of course, is that you don't need 3. So, the idea of this next approach is to maintain a separate list that is essentially the longest subsequence of the array. For every number we pass, if the number is greater than any value we have seen, we can add it to the list. If the number is less than a value we have seen, we can replace it at the given index in our maintained list. This is a beautiful use-case of Binary Search.

tails = []
for x in nums:
	i = bisect_left(tails, x)
	if i == len(tails)
		tails.append(x)
	else:
		tails[i] = x
return len(tails)

What is super interesting here is that even if you replace an element at the start of the array, len(tails) is still valid as an answer because tails has still built the largest subsequence so far. If future values continue to replace and add onto the array, then we will have a new subsequence, but tails is guaranteed to always represent the longest subsequence we have seen so far.