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