Solution to Eleanor's ordered sequence problem

sequence.py

#!/usr/bin/env python

class Node(object):
  def __init__(self, value):
    self.value = value
    self.left = self.right = None
    self.first = self.last = self

  def __repr__(self):
    return "Node(value=%d, first=%d, last=%d)" % (self.value, self.first.value, self.last.value)


def longest_contiguous_subsequence(nums):
  r"""
  Given a sequence of unique integers, determine the length of the longest
  contiguous subsequence of the integers supposing that they were sorted.
  """
  h = {}

  for num in nums:
    (left, right) = h.get(num, (None, None))
    node = Node(num)

    if left and right:
      # The new node is in the middle of a list, let's link this node into
      # the middle.
      node.left = left
      left.right = node

      node.right = right
      right.left = node

      # Figure out the beginning of this sublist and the end of this sublist
      # and make sure the outermost nodes of the sublist are correct with
      # respect to first and last
      first = left.first
      last = right.last
      first.last = last
      last.first = first
    elif left:
      # The new node is at the end of a list, let's link this node into place
      node.left = left
      left.right = node

      # Figure out the beginning of this sublist and the end of this sublist
      # and make sure the outermost nodes of the sublist are correct with
      # respect to first and last
      first = left.first
      last = node
      first.last = last
      last.first = first
    elif right:
      # The new node is at the start of a list, let's link this node into place
      node.right = right
      right.left = node

      # Figure out the beginning of this sublist and the end of this sublist
      # and make sure the outermost nodes of the sublist are correct with
      # respect to first and last
      first = node
      last = right.last
      first.last = last
      last.first = first
    else:
      # This node is the entire list by itself
      node.first = node.last = node

    # Now that we've built a list out of the nodes, we need to save it in the
    # hash table in a spot that's ready to go for the next nodes.
    first = node.first
    last = node.last

    left = h.get(num-1, (None, None))
    h[num-1] = (left[0], first)

    right = h.get(num+1, (None, None))
    h[num+1] = (first, right[1])
    if num in h:
      del h[num]

  nodes = [left for (left, right) in h.values() if left] + \
          [right for (left, right) in h.values() if right]
  return max(nodes, key=lambda node: node.last.value - node.first.value)


TESTS = [
  [1],
  [1, 2],
  [1, 10],
  [1, 2, 3],
  [3, 2, 1],
  [1, 3, 2],
  [3, 1, 2],
  [4, 2, 5, 3, 9, 7, 12, 1],
  [1, 3, 5, 7, 9],
  [1, 3, 6, 4, 5, 9, 8, 12]
]

for test in TESTS:
  print "input: ", test
  print "sorted:", sorted(test)
  print "answer:", longest_contiguous_subsequence(test)
  print