Description

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Solutions

1. DP

  采用动态规划的解决方法,维护一个 dp 数组,其中 dp[i] 表示以 nums[i] 结尾的最长递增字串长度,对于每一个 nums[i],我们从第一个数再搜索到 i,如果发现某个数小于 nums[i],我们就更新 dp[i],更新方法是 dp[i] = max(dp[i], dp[j] + 1),即比较当前 dp[i] 的值和那个小于 num[i] 的数的 dp 值加 1 的大小,我们就这样不断的更新 dp数组,到最后 dp 数组中最大的值就是我们要返回的 LIS 的长度。

# Time: O(n^2)
# Space: O(n)
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        dp = [1 for _ in range(n)]
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
# 24/24 cases passed (1224 ms)
# Your runtime beats 21.57 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)

2. 加上 Binary Search 提升到 O(nlogn)

  按照前人的思考,我们可以维护一个数组 tails 用来存储不同大小下的子序列最小的那个元素,tails[i] 表示长度为 i+1 的子序列中最小的最后一个数。举个栗子,当 nums = [4,5,6,3] 时:

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

  因为不同大小的子序列下都是取最小元素,能想到 tails 数组肯定是递增的。那么在往后遍历时,我们就需要更新 tails 数组,在找合适位置更新时就可以用到二分法了。

  每一步我们都是采取下述其中之一的方式进行操作,遍历完得到最后的 tails 数组大小即可:

1. 如果 x 大于 tails 中所有的数那么直接 append x  tails 大小增 1 即可
2. 如果 tails[i-1] < x <= tails[i]那么更新 tails[i]
# Time Complexity: O(nlogn)
# Space Complexity: O(n)
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = [0] * len(nums)
        size = 0
        for x in nums:
            i, j = 0, size
            while i != j:
                m = (i + j) >> 1
                if tails[m] < x:
                    i = m + 1
                else:
                    j = m
            tails[i] = x
            size = max(i + 1, size)
        return size
# Runtime: 44 ms, faster than 96.94% of Python3 online submissions for Longest Increasing Subsequence.
# Memory Usage: 13.8 MB, less than 5.13% of Python3 online submissions for Longest Increasing Subsequence.

  可以将上述解法修改成保存 tails 数组的方式

# Time Complexity: O(nlogn)
# Space Complexity: O(n)
class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tails = []
        n = len(nums)
        for i in range(n):
            left, right = 0, len(tails)
            while left < right:
                mid = (left + right) >> 1
                if tails[mid] < nums[i]:
                    left = mid + 1
                else:
                    right = mid
            if right >= len(tails):
                tails.append(nums[i])
            else:
                tails[left] = nums[i]
        return len(tails)
# Runtime: 52 ms, faster than 79.46% of Python3 online submissions for Longest Increasing Subsequence.
# Memory Usage: 14.1 MB, less than 5.13% of Python3 online submissions for Longest Increasing Subsequence.

  最优解:其实dp数组是单调递增,所以可以把内存循环的比较过程改成二分查找的方式,二分的时间复杂度为O(logn),所以优化后的时间复杂度是O(nlogn)。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        dp = []
        for i in range(n):
            idx = self.binary_search(dp, nums[i])
            if idx == len(dp):
                dp.append(nums[i])
            else:
                dp[idx] = nums[i]
        return len(dp)
    
    def binary_search(self, dp, target):
        if len(dp) == 0:
            return 0
        l, r = 0, len(dp) - 1
        if dp[r] < target:
            return len(dp)
        while l <= r:
            mid = l + ((r - l) >> 1)
            if dp[mid] >= target:
                r = mid - 1
            else:
                l = mid + 1
        return l

References

  1. 300. Longest Increasing Subsequence
  2. Longest Increasing Subsequence
  3. Longest Increasing Subsequence 最长递增子序列
  4. Java/Python Binary search O(nlogn) time with explanation
  5. huahua