首页 > 其他 > 详细

Leetcode 300. Longest Increasing Subsequence

时间:2019-09-17 19:52:36      阅读:73      评论:0      收藏:0      [点我收藏+]

https://leetcode.com/problems/longest-increasing-subsequence/

Medium

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?


技术分享图片
 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)
View Python Code

 

Leetcode 300. Longest Increasing Subsequence

原文:https://www.cnblogs.com/pegasus923/p/11536482.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!