Solutions

# DFS with memorization (pick or skip the element), or DP bottom-up (for each element, find the longest increasing subsequence starting at that element)
# dp

# DP bottom-up - O(n^2) time, O(n) space
def lengthOfLIS(nums: list[int]) -> int:
    # LIS[i] = length of longest increasing subsequence starting at index i
    LIS = [1] * len(nums)

    for i in range(len(nums)-1, -1, -1):
        for j in range(i+1, len(nums)):
            if nums[i] < nums[j]:
                LIS[i] = max(LIS[i], 1 + LIS[j])

    return max(LIS)
    

# DFS with memoization - O(n^2) time, O(n^2) space
# would be O(2^n) time without memoization
def lengthOfLIS1(nums: list[int]) -> int:
    N = len(nums)
    cache = {}

    def dfs(i: int, prev_i: int):
        if i >= N:
            return 0

        if (i, prev_i) in cache:
            return cache[(i,prev_i)]

        # skip the number (always)
        LIS = dfs(i+1, prev_i)

        # pick the number (if it's greater than previous, or if it's the first)
        if prev_i == -1 or nums[i] > nums[prev_i]:
            LIS = max(LIS, 1 + dfs(i+1, i))

        cache[(i,prev_i)] = LIS
        return LIS

    return dfs(0, -1)


# Dynamic programming with binary search (HARD) - O(n log n) time, O(n) space
def lengthOfLIS2(nums: list[int]) -> int:
    # LIS[i] = the smallest number that ends an increasing subsequence of length i+1
    LIS = []

    for num in nums:
        # find the index of the smallest number in LIS that is greater than or equal to num
        left, right = 0, len(LIS)
        while left < right:
            mid = (left + right) // 2
            if LIS[mid] < num:
                left = mid + 1
            else:
                right = mid

        # if num is greater than all elements in LIS, append it
        if left == len(LIS):
            LIS.append(num)
        # otherwise, replace the element at index left with num
        else:
            LIS[left] = num

    return len(LIS)