Problem of The Day: Longest Increasing Subsequence

Problem Statement

leetcode problem link

My Solution [MLE]

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        @cache
        def dp(i, curr, j):
            if i == len(nums):
                return curr
            res = 0
            # Allow taking element when j == -1 (no element taken yet) OR when strictly increasing
            if j == -1 or nums[i] > nums[j]:
                res = max(res, dp(i + 1, curr + 1, i))
            res = max(res, dp(i + 1, curr, j))

            return res


        return dp(0, 0, -1)  # Start with no elements taken (curr=0, j=-1)

Improve Algorithm [Accepted]

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)

        @cache
        def dfs(i):
            # LIS ending at i
            best = 1
            for j in range(i):
                if nums[j] < nums[i]:
                    best = max(best, dfs(j) + 1)
            return best

        return max(dfs(i) for i in range(n))

Editorial

Approach 1: Dynamic Programming

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)