class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#list to keep track of the longest increasing list, the elements are only as placeholders, they are not necessarily the actual longest increasing list
#dynamic programming: everytime we scan a number, the status of which is recorded in the LIS
LIS=[]
def insert(target):
#use binary search to find the index of the element in LIS that is no less than the target
left,right=0,len(LIS)-1
while left<=right:
mid=left+(right-left)/2
if LIS[mid]>=target:
right=mid-1
else:
left=mid+1
#if all the elements in the LIS is smaller than the target, then append the target to LIS
if left==len(LIS):
LIS.append(target)
else:#otherwise, replace the element in the LIS with target, this does not affect the length of the actual LIS already found, but it would not be the actual LIS.
#all the elements after the replaced elements become placeholders that keep track of length of the previously found LIS. when we've replaced all the elements on and after the target elements, we've located a new LIS.
LIS[left]=target
for num in nums:
insert(num)
return len(LIS)
300. Longest Increasing Subsequence
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Longest Increasing Subsequence给定一个数组，找出longest increasing...
- Given an unsorted array of integers, find the length of l...
- 问题描述 Given an unsorted array of integers, find the length...
- 从第一个开始检查，注意，并不是指连续的序列。详见题目：https://leetcode.com/problems/...
- d[i] i为结尾的最长递增子序列，d[0] = 1 ,d[i] 算出 [0,i) 找出d[i] > d[[0,i...
