old_contents: """LongestIncreasingSubsequence.py
  
  Find longest increasing subsequence of an input sequence.
  D. Eppstein, April 2004
  """
  
  import unittest
  from bisect import bisect_left
  
  def LongestIncreasingSubsequence(S):
      """
      Find and return longest increasing subsequence of S.
      If multiple increasing subsequences exist, the one that ends
      with the smallest value is preferred, and if multiple
      occurrences of that value can end the sequence, then the
      earliest occurrence is preferred.
      """
  
      # The main data structures: head[i] is value x from S that
      # terminates a length-i subsequence, and tail[i] is either
      # None (if i=0) or the pair (head[i-1],tail[i-1]) as they
      # existed when x was processed.
      head = []
      tail = [None]
  
      for x in S:
          i = bisect_left(head,x)
          if i >= len(head):
              head.append(x)
              if i > 0:
                  tail.append((head[i-1],tail[i-1]))
          elif head[i] > x:
              head[i] = x
              if i > 0:
                  tail[i] = head[i-1],tail[i-1]
  
      if not head:
          return []
  
      output = [head[-1]]
      pair = tail[-1]
      while pair:
          x,pair = pair
          output.append(x)
  
      output.reverse()
      return output
  
  # If run as "python LongestIncreasingSubsequence.py", run tests on various
  # small lists and check that the correct subsequences are generated.
  
  class LISTest(unittest.TestCase):
      def testLIS(self):
          self.assertEqual(LongestIncreasingSubsequence([]),[])
          self.assertEqual(LongestIncreasingSubsequence(range(10,0,-1)),[1])
          self.assertEqual(LongestIncreasingSubsequence(range(10)),range(10))
          self.assertEqual(LongestIncreasingSubsequence([3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]),
                                                        [1,2,3,5,8,9])
  
  if __name__ == "__main__":
      unittest.main()   
  
new_contents: """LongestIncreasingSubsequence.py
  
  Find longest increasing subsequence of an input sequence.
  D. Eppstein, April 2004
  """
  
  import unittest
  from bisect import bisect_left
  
  def LongestIncreasingSubsequence(S):
      """
      Find and return longest increasing subsequence of S.
      If multiple increasing subsequences exist, the one that ends
      with the smallest value is preferred, and if multiple
      occurrences of that value can end the sequence, then the
      earliest occurrence is preferred.
      """
  
      # The main data structures: head[i] is value x from S that
      # terminates a length-i subsequence, and tail[i] is either
      # None (if i=0) or the pair (head[i-1],tail[i-1]) as they
      # existed when x was processed.
      head = []
      tail = [None]
  
      for x in S:
          i = bisect_left(head,x)
          if i >= len(head):
              head.append(x)
              if i > 0:
                  tail.append((head[i-1],tail[i-1]))
          elif head[i] > x:
              head[i] = x
              if i > 0:
                  tail[i] = head[i-1],tail[i-1]
  
      if not head:
          return []
  
      output = [head[-1]]
      pair = tail[-1]
      while pair:
          x,pair = pair
          output.append(x)
  
      output.reverse()
      return output
  
  # If run as "python LongestIncreasingSubsequence.py", run tests on various
  # small lists and check that the correct subsequences are generated.
  
  class LISTest(unittest.TestCase):
      def testLIS(self):
          self.assertEqual(LongestIncreasingSubsequence([]),[])
          self.assertEqual(LongestIncreasingSubsequence(range(10,0,-1)),[1])
          self.assertEqual(LongestIncreasingSubsequence(range(10)),
                                                        list(range(10)))
          self.assertEqual(LongestIncreasingSubsequence([3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]),
                                                        [1,2,3,5,8,9])
  
  if __name__ == "__main__":
      unittest.main()   
  
  
subject: Update LongestIncreasingSubsequence for Python3 compatibility