Longest Increasing Subsequence

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.

  • For example, "cat" is a subsequence of "crabt".

Example 1:

# Input: nums = [9,1,4,2,3,3,7]
# Output: 4
nums = [9, 1, 4, 2, 3, 3, 7]
print(len(longest_increasing_subsequence(nums)))

Explanation: The longest increasing subsequence is [1,2,3,7], which has a length of 4.

Example 2:

# Input: nums = [0,3,1,3,2,3]
# Output: 4
nums = [0, 3, 1, 3, 2, 3]
print(len(longest_increasing_subsequence(nums)))

Constraints:

  • 1 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000

You should aim for a solution with O(n \log n) time.

Solution

Recursion

def longest_increasing_subsequence(nums: list[int]) -> int:
    def dfs(i, j):
        if i == len(nums):
            return 0


        lis = dfs(i + 1, j)  # Not include


        if j == -1 or nums[j] < nums[i]:
            lis = max(lis, 1 + dfs(i + 1, i))  # Include


        return lis


    return dfs(0, -1)

Time complexity: O(2 ^ n) Space complexity: O(n)