300 - Longest Increasing Subsequence
Written on October 21, 2015
Tweet
Given a sequence of integers, find the longest increasing subsequence (LIS). You code should return the length of the LIS.
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
ret = []
for num in nums:
index = self.find_index(ret, num)
if index < len(ret):
ret[index] = num
else:
ret.append(num)
return len(ret)
def find_index(self, nums, num):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) / 2
if nums[mid] < num:
lo = mid + 1
else:
hi = mid - 1
return lo