Given an unsorted array of integers, find the length of the longest increasing subsequence (LIS).

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

Function Signature:

from typing import List

def length_of_lis(nums: List[int]) -> int:
    """
    Find the length of the longest increasing subsequence.

    Parameters:
    - nums: A list of integers.

    Returns:
    - int: The length of the longest increasing subsequence.
    """
    # Your code here

Example:

# Input: nums = [0, 1, 2, 3]
# Output: 4
# Explanation: The whole input sequence of length 4 is increasing.

# Input: nums = [0, 1, 3, 10, 2, 3, 4]
# Output: 5
# Explanation: The longest increasing subsequence is [0, 1, 2, 3, 4], so the
#              length is 5.

# Input: nums = [10, 9, 2, 5, 3, 7, 101, 18, 105]
# Output: 5
# Explanation: The longest increasing subsequence is [2, 3, 7, 101, 105], so
#              the length is 5.

Note:

  • There may be more than one LIS combination. It is only necessary for you to return the length.

Instructions:

  • Write the length_of_lis function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊