human
Write me a Python code to find the length of longest increasing subsequence given the following:
Solve in Python:
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?
assistant
#Here is Python code to find the length of longest increasing subsequence.

class Solution:
     def lengthOfLIS(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         dp = [float('inf')] * (n + 1)
         res = 0
         
         for num in nums:
             # like finding inerstion position             
             lo, hi = 1, n
             while lo < hi:
                 mi = int((lo + hi) / 2)
                 if dp[mi] < num:
                     lo = mi + 1
                 else:
                     hi = mi
             dp[lo] = num
             res = max(res, lo)
         return res