LC300 - Longest Increasing Subsequence

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. Note that the subsequence does not need to be contiguous.

Example

Input: nums = [10,9,2,5,3,7,101,18]

Output: 4

Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Solution

DFS

Use DFS to generate all possible subsequences by having a decision tree, where each array index is a node, and the leaves are the indices that can be added to the subsequence. However this is really expensive due to the deep LIS call stack, which gives a time complexity of $O(2^n)$.

Cached DFS

Since there are repeated calls to find the LIS of the same index/subtree, we can use the @cache decorator to reduce compute. Time complexity of this approach is $O(n^2)$, because repeated calls to LIS with the same argument returns cached results. We use $O(n)$ extra space for the cache.

def lengthOfLIS(self, nums: List[int]) -> int:
	@cache
	def LIS(i):
		# if i is len(nums)-1, return 1
		if i == len(nums) - 1:
			return 1
		# else, return max of 1, 1+LIS(i+1), ..., 1+LIS(n)
		else:
			tmpArr = [1]
			​for j in range(i+1, len(nums)):
				if nums[j] > nums[i]:
					tmp = 1 + LIS(j)
					tmpArr.append(tmp)
			return max(tmpArr)

	for i in range(len(nums)):
		tmpArr.append(LIS(i))
	return max(tmpArr)