output_description: For each dataset, print the maximum sum in a line.
input_description: The input consists of multiple datasets. Each data set consists of:
  
      
      
      n
      a1
      a2
      .
      .
      an
      
  
  You can assume that 1 ≤ n ≤ 5000 and -100000 ≤ ai ≤ 100000\.
  
  The input end with a line consisting of a single 0.
attempt: class Node:
      prev = next = None
  
      def __init__(self, value):
          self.value = value
  
      def get_nxnx(self):
          next_n = self.next
          if not next_n:
              return None, None
          return next_n, next_n.next
  
      def get_prpr(self):
          prev_n = self.prev
          if not prev_n:
              return None, None
          return prev_n, prev_n.prev
  
      def combine(self):
          next_n, nxnx_n = self.get_nxnx()
          if not next_n or not nxnx_n:
              return False
  
          if self.value > abs(next_n.value) < nxnx_n.value:
              self.value += next_n.value + nxnx_n.value
              self.next = nxnx_n.next
              _, prpr = self.get_prpr()
              if prpr:
                  prpr.combine()
              return True
          return False
  
      def iter(self):
          a = self
          while a:
              yield a.value
              a = a.next
  
  
  while True:
      n = int(input())
      if not n:
          break
      a0 = a = Node(int(input()))
      n -= 1
      while n:
          an = int(input())
          if an * a.value < 0:
              at = Node(an)
              at.prev = a
              a.next = at
              a = at
          else:
              a.value += an
          n -= 1
      if a0.value < 0:
          a0 = a0.next
      a = a0
      while a:
          while a.combine():
              pass
          _, a = a.get_nxnx()
      print(max(v for v in a0.iter()))
  
problem_description: Maximum Sum Sequence
  
  Given a sequence of numbers a1, a2, a3, ..., an, find the maximum sum of a
  contiguous subsequence of those numbers. Note that, a subsequence of one
  element is also a _contiquous_ subsequence.
samples: [{"input": "-5\n    -1\n    6\n    4\n    9\n    -6\n    -7\n    13\n    1\n    2\n    3\n    2\n    -2\n    -1\n    1\n    2\n    3\n    2\n    1\n    -2\n    1\n    3\n    1000\n    -200\n    201\n    0", "output": "14\n    1001"}]