Skip to content

Instantly share code, notes, and snippets.

@csujedihy
Created March 8, 2017 06:56
Show Gist options
  • Save csujedihy/07d8c7fc917fedff618a0f9774c0b45f to your computer and use it in GitHub Desktop.
Save csujedihy/07d8c7fc917fedff618a0f9774c0b45f to your computer and use it in GitHub Desktop.
LIS
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
tail = []
for i in xrange(0, len(nums)):
idx = bisect.bisect_right(tail, nums[i])
if idx - 1 >= 0 and nums[i] == tail[idx - 1]:
continue
if idx == len(tail):
tail.append(nums[i])
else:
tail[idx] = nums[i]
return len(tail)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment