old_contents: # Time:  O(nlogn)
  # Space: O(n)
  #
  # Given an unsorted array of integers, 
  # find the length of longest increasing subsequence.
  #
  # For example,
  # Given [10, 9, 2, 5, 3, 7, 101, 18],
  # The longest increasing subsequence is [2, 3, 7, 101],
  # therefore the length is 4. Note that 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?
  #
  
  # Binary search solution.
  class Solution(object):
      def lengthOfLIS(self, nums):
          """
          :type nums: List[int]
          :rtype: int
          """
          LIS = []
          def insert(target):
              left, right = 0, len(LIS) - 1
              # Find the first index "left" which satisfies LIS[left] >= target
              while left <= right:
                  mid = left + (right - left) / 2;
                  if LIS[mid] >= target:
                      right = mid - 1
                  else:
                      left = mid + 1
              # If not found, append the target.
              if left == len(LIS):
                  LIS.append(target);
              else:
                  LIS[left] = target
  
          for num in nums:
              insert(num)
  
          return len(LIS)
  
new_contents: # Time:  O(nlogn)
  # Space: O(n)
  #
  # Given an unsorted array of integers, 
  # find the length of longest increasing subsequence.
  #
  # For example,
  # Given [10, 9, 2, 5, 3, 7, 101, 18],
  # The longest increasing subsequence is [2, 3, 7, 101],
  # therefore the length is 4. Note that 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?
  #
  
  # Binary search solution.
  class Solution(object):
      def lengthOfLIS(self, nums):
          """
          :type nums: List[int]
          :rtype: int
          """
          LIS = []
          def insert(target):
              left, right = 0, len(LIS) - 1
              # Find the first index "left" which satisfies LIS[left] >= target
              while left <= right:
                  mid = left + (right - left) / 2;
                  if LIS[mid] >= target:
                      right = mid - 1
                  else:
                      left = mid + 1
              # If not found, append the target.
              if left == len(LIS):
                  LIS.append(target);
              else:
                  LIS[left] = target
  
          for num in nums:
              insert(num)
  
          return len(LIS)
  
  # Time:  O(n^2)
  # Space: O(n)
  # Traditional DP solution.
  class Solution2(object):
      def lengthOfLIS(self, nums):
          """
          :type nums: List[int]
          :rtype: int
          """
          dp = []
          for i in xrange(len(nums)):
              dp.append(1)
              for j in xrange(i):
                  if nums[j] < nums[i]:
                      dp[i] = max(dp[i], dp[j] + 1)
          return max(dp) if dp else 0
  
subject: Update longest-increasing-subsequence.py