300. Longest Increasing Subsequence

Loading...LeetCode

乍一看以为subsequence要连续，还想用 sliding window做，一看example，可以不连续。

允许不连续的话，就可以递归解，当前列的最长subsequece，取决于当前列最后一个元素，以及去掉这个元素的子列的关系。逻辑有点绕，写出来仿佛写了个假dp...

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1: return n
        memo = collections.defaultdict(lambda : 1)
        
        def getLIS(idx):
            if idx in memo.keys(): return memo[idx]
            for l in range(idx):
                if nums[l] < nums[idx]:
                    memo[idx] = max(memo[idx], getLIS(l)+1)
            return memo[idx]
        
        for r in range(1, n):
            getLIS(r)
            
        return max(memo.values())

看到O(n*logn) 的解法了，DP + Binary Search，不写了。