https://leetcode.com/problems/longest-increasing-subsequence/
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 is4.
Note:
Follow up: Could you improve it to O(n log n) time complexity?
1 class Solution: 2 def lengthOfLIS1(self, nums: List[int]) -> int: 3 if not nums: 4 return 0 5 6 dp = [1] * len(nums) 7 8 for i in range(len(nums)): 9 for j in range(i): 10 if nums[i] > nums[j]: 11 dp[i] = max(dp[i], dp[j] + 1) 12 13 # should be the maximum element of dp 14 return max(dp) 15 16 def lengthOfLIS(self, nums: List[int]) -> int: 17 if not nums: 18 return 0 19 20 tails = [] 21 22 for num in nums: 23 left, right = 0, len(tails) - 1 24 25 # find the first index "left" where tails[left] >= num 26 while left <= right: 27 middle = (left + right) // 2 28 if num <= tails[middle]: 29 right = middle - 1 30 else: 31 left = middle + 1 32 33 # if num is larger than all tails, append it 34 if left == len(tails): 35 tails.append(num) 36 # if tails[left-1] < num <= tails[left], update tails[left] 37 else: 38 tails[left] = num 39 40 return len(tails)
Leetcode 300. Longest Increasing Subsequence
原文：https://www.cnblogs.com/pegasus923/p/11536482.html
