LeetCode 300. Longest Increasing Subsequence

longest_increasing_subsequence.py

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

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. For
example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
"""
from typing import List


def lengthOfLIS(nums: List[int]) -> int:

    nums_len = len(nums)
    last_idx = nums_len - 1

    # Degenerate case
    if nums_len == 0:
        return 0

    # Recursive function builds lookup dictionary (indices -> subsequence lengths)
    memo = {idx: 0 for idx in range(nums_len)}

    def index_lengthOfLIS(idx: int) -> int:
        """
        Returns the length of LIS starting at index `idx` on `nums`
        """
        # Base case(s)
        if idx == last_idx:
            memo[idx] = 1
        if memo[idx]:
            return memo[idx]

        # Recursive case
        longest_subseq_len = 0
        for i in range(last_idx, idx, -1):
            subseq_len = 1
            if nums[i] > nums[idx]:
                subseq_len += index_lengthOfLIS(i)
            longest_subseq_len = max(subseq_len, longest_subseq_len)
        memo[idx] = longest_subseq_len
        return memo[idx]

    return max(index_lengthOfLIS(idx) for idx in range(nums_len))


def main(nums: List[int]):
    print(f"LIS length: {lengthOfLIS(nums)}")


if __name__ == "__main__":
    test_cases = [
        [],  # 0
        [-20],  # 1
        [1, 20, 3, 50, 7],  # 3
        [0, 3, 1, 6, 2, 2, 7],  # 4
        [10, 9, 2, 5, 3, 7, 101, 18],  # 4
        [0, 1, 0, 3, 2, 3],  # 4
        [7, 7, 7, 7, 7, 7, 7, 7],  # 1
        [-23, 45, 23, -34, 5, 2, 3, 6, 8, 20, 5009],  # 7
    ]
    for test in test_cases:
        main(test)

Note that the memoized recursive solution is still time complexity $O(n^{2})$. There is a better, $O(n \ log_{2}{n})$ implementation described here.