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?
class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         import bisect
         
         d = [0] * len(nums)
         
         maxLen = 0
         
         for n in nums:
           i = bisect.bisect_left(d, n, 0, maxLen)
           if i == maxLen:
             maxLen += 1
           d[i] = n
         return maxLen
class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         import bisect
         
         d = [0] * len(nums)
         
         maxLen = 0
         
         for n in nums:
           i = bisect.bisect_left(d, n, 0, maxLen)
           if i == maxLen:
             maxLen += 1
           d[i] = n
         return maxLen