leetcode300-- Longest increasing Subsequence.(LIS)(注意O(nlogn)解法)

# 小郑之家~

### 题目


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?



###

dp[i] = max(dp[i], dp[j]+1), 其中j<i并且nums[j]<nums[i].

class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = [1]*len(nums)

ret = 0

for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j]+1);

ret = max(ret, dp[i])

return ret



class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

if len(nums)==0:
return 0
ends = [nums[0]]

for i in range(len(nums)):
# 看当前的元素，
# 如果比ends的首元素小，就换掉
if (nums[i]<ends[0]):
ends[0] = nums[i]
# 如果比最后一个元素大的话，就放到最后
elif nums[i]> ends[-1]:
ends.append(nums[i])
# 如果是在首元素和尾元素之间的话,
else:
left = 0
right = len(ends)
# 二分查找找到其应该在的位置
while(left<right):
mid = left +(right-left)/2
if(ends[mid]<nums[i]):
left = mid+1  # 注意是加1.
else:
right = mid
ends[right] = nums[i]
return len(ends)