162 - 300 最长上升子序列

题目

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

• 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解答

暴力法就是把所有的上升子数组都求出来。

暴力

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def helper(pre, cur):
            if cur == len(nums):
                return 0
            taken = 0
            if nums[cur] > pre:
                taken = 1+helper(nums[cur], cur+1)
            untaken = helper(pre, cur+1)
            return max(taken, untaken)
        return helper(float('-inf'), 0)

超时

动态规划

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-she-ji-fang-fa-zhi-pai-you-xi-jia/

dp数组存当前数字最长上升子序列。

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

Runtime: 1172 ms, faster than 23.13% of Python3 online submissions for Longest Increasing Subsequence.

Memory Usage: 13 MB, less than 100.00% of Python3 online submissions for Longest Increasing Subsequence.

var lengthOfLIS = function(nums) {
  const len = nums.length
  if (len <= 1) {
    return len
  }
  let dp = new Array(len);
  for (let i = 0; i < len; i++) {
    dp[i] = 1
  }
  let ans = 1
  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
    ans = Math.max(ans, dp[i])
  }
  return ans
};

Runtime: 72 ms, faster than 59.59% of JavaScript online submissions for Longest Increasing Subsequence.

Memory Usage: 34.8 MB, less than 55.56% of JavaScript online submissions for Longest Increasing Subsequence.

二分查找

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        top = [0]*len(nums)
        piles = 0
        for i in range(0, len(nums)):
            left = 0
            right = piles
            while left < right:
                mid = (left+right) >> 1
                if top[mid] < nums[i]:
                    left = mid+1
                else:
                    right = mid
            if left == piles:
                piles += 1
            top[left] = nums[i]
        return piles

Runtime: 32 ms, faster than 99.55% of Python3 online submissions for Longest Increasing Subsequence.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Longest Increasing Subsequence.