300. Longest Increasing Subsequence

Loading...LeetCode

brute force 做的话，最无脑方法就是对每个位置有两个选择取或不取，最后有 2**n 个subsequence要判断，肯定不行。改进一点就是做个类似backtracking的判断，当前新进元素大于 subsequence 前值，则可以加入，但 worst case 的复杂度仍然没变。

Dynamic Programming

其实还是能比较容易地看出是bottom-up DP，但状态转换方程比较难想：

$$dp[i]=max(dp[j])+1,∀0≤j<i$$

即对每个新进元素i，nums[:i+1]的LIS肯定是i前面某一元素j的LIS+1(dp[j]+1)，有了转换方程的话就不难写了。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if not n: return 0
        
        dp = [0 for _ in range(n)]
        maxL = dp[0] = 1
        
        for i in range(1, n):
            submax = 0
            for j in range(i):
                if nums[j] < nums[i]:
                    submax = max(submax, dp[j])
            dp[i] = submax + 1
            maxL = max(maxL, dp[i])
        return maxL

Binary Search

原来这题最好的解法是二分...需要借助这个特征：

Increasing subsequence 尾元素大小随着 subsequence 长度递增

比如：

len = 1   :      [4], [5], [6], [3]   => tails[0] = 3
len = 2   :      [4, 5], [5, 6]       => tails[1] = 5
len = 3   :      [4, 5, 6]            => tails[2] = 6

然后只要遍历nums中元素，如果当前元素x大于所有的tail，则把x加进 increasing subsequence，并且 size++，否则，需要找到i使得tails[i-1]<x<=tails[i]，然后用x更新tails[i]，这边就是使用 binary search。

其实我觉得面试能想出这个解法也不太可能，留个档练练二分搜索吧...

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = [0 for _ in range(len(nums))]
        size = 0
        for x in nums:
            i, j = 0, size
            while i != j:
                m = (i + j) // 2
                if tails[m] < x:
                    i = m + 1
                else:
                    j = m
            tails[i] = x
            size = max(i + 1, size)
        return size