Longest Increasing Subsequence [LC#300]

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Dynamic programming approach

• Find the length of longest increasing subsequence ending at i.

  def length_of_lis(nums: List[int]) -> int:
      if not nums: return 0
      max_length = [1] * len(nums)
      for i in range(1, len(nums)):
          for j in range(i):
              if nums[i] > nums[j]:
                  max_length[i] = max(max_length[i], max_length[j] + 1)
      return max(max_length)
  

• $T(n) + O(n^2)$; $S(n) = O(n)$

Technique based on patience sorting

• If the number is larger than the largest element in the temporary array, append it. Otherwise, replace the found position with the current number.
• The length of the temporary array will give the length of the longest increasing subsequence.
• The temp array may not always have a valid subsequence, but its length will always be equal to longest subsequence.

  from bisect import bisect_left
  
  def length_of_lis(nums: List[int]) -> int:
      if not nums: return 0
      tails = []
      for num in nums:
          pos = bisect_left(tails, num)
          if pos == len(tails):
              tails.append(num)
          else:
              tails[pos] = num
      return len(tails)
  

• $T(n) = O(n \log n)$; $S(n) = O(n)$