Problem:
Maximum Sum Sequence Given a sequence of numbers a 1 , a 2 , a 3 , ..., a n , find the maximum sum of a contiguous subsequence of those numbers. Note that, a subsequence of one element is also a contiquous subsequence. Input The input consists of multiple datasets. Each data set consists of:  n  a 1  a 2 .
. a n   You can assume that 1 ≤ n ≤ 5000 and -100000 ≤ a i ≤ 100000.  The input end with a line consisting of a single 0.  Output  For each dataset, print the maximum sum in a line.  Sample Input  7
-5
-1
6
4
9
-6
-7
13
1
2
3
2
-2
-1
1
2
3
2
1
-2
1
3
1000
-200
201
0  Output for the Sample Input  19
14
1001

Solution (Python):
n=input()
while n:
    x=[]
    m=[]
    s=0
    for i in range(n):
        a=input()
        x=[e+a for e in x]+[a]
        m.append(max(x))
    print max(m)
    n=input()

Solution (Python):
n=input()
while n:
    x=-100000
    m=x
    s=0
    while n:
        a=input()
        x=max(x,0)+a
        m=max(m,x)
        n-=1
    print m
    n=input()

Solution (Python):
n=input()
while n:
    x=-100000
    m=x
    s=0
    while n:
        x=input()+max(0,x)
        m=max(m,x)
        n-=1
    print m
    n=input()

Solution (Python):
while True:
    n = int(raw_input())
    if n == 0:
        break
    a = [0]
    for i in range(n):
        a.append(int(raw_input()) + a[-1])
    mx = -100000
    for i in range(n):
        for j in range(i + 1, n + 1):
            mx = max(mx, a[j] - a[i])
    print mx

Solution (Python):
while True:
  n = int(raw_input())
  if n == 0: break
  max_n = max_m = -100000
  r = 0

  for i in range(n):
    m = int(raw_input())
    max_n = max(max_n, m)
    r = max(r+m, 0)
    max_m = max(max_m, r)

  if max_n > 0:
    print max_m
  else:
    print max_n

Solution (Python):

while 1:
    n = input()
    if n == 0:
        break
    A = []
    for i in xrange(n):
        A.append(int(raw_input()))
    dp = [0] * len(A)
    dp[0] = A[0]
    for i in xrange(1, len(A)):
        dp[i] = max(dp[i - 1] + A[i], A[i])
    print max(dp)

Solution (Python):
while 1:
    n = int(raw_input())
    if n == 0:
        break
    A = [0] * n
    for i in xrange(n):
        A[i] = int(raw_input())
    for i in xrange(1, len(A)):
        A[i] = max(A[i - 1] + A[i], A[i])
    print max(A)

Solution (Python):
while True:
    n = int(input())
    if n == 0: break
    a = []
    for i in range(n):
        a.append(int(input()))
    for i in range(1, n):
        a[i] = max(a[i - 1] + a[i], a[i])
    print(max(a))

Solution (Python):
def maximumSubArray(array):
    n = len(array)
    dp = [0]*n 
    dp[0] = array[0]
    for i in range(1, n):
        dp[i] = max(dp[i - 1] + array[i], array[i])
    return max(dp)

while True:
    n = int(input())
    a = []
    if n == 0:
        break
    for _ in range(n):
        a.append(int(input()))
    print(maximumSubArray(a))

Solution (Python):

import sys,bisect
sys.setrecursionlimit(15000)

st = []
ar = 0
while True:
   n = int(sys.stdin.readline())
   if n == 0:
     break
   a = [int(sys.stdin.readline()) for _ in range(n)]
   ml = mg = a[0]
   
   for i in range(1,n):
     ml = max(ml+a[i],a[i])
     mg = max(mg,ml)
     
   print(mg)

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(readline())
    if N == 0:
        return False
    mi = su = 0
    ans = -10**9
    for i in range(N):
        a = int(readline())
        su += a
        ans = max(ans, su - mi)
        mi = min(su, mi)
    print(ans)
    return True
while solve():
    ...

Solution (Python):
while 1:
    try:
        n = int(input())
    except:break
    
    if(n == 0):break

    sum = 0
    arr = []
    isPlus = True
    maxValue = -100000
    for i in range (n):
        try:
            arr.append(int(input()))  
        except:break
           
        if arr[i] < 0:
            
            if sum > 0:
                
                if(isPlus):
                    
                    maxValue = max(maxValue,sum)
                    isPlus = False
                sum += arr[i]
                
                if sum < 0 :
                    sum = 0
        else :
            sum += arr[i]
            isPlus = True
    if sum != 0 :
        maxValue = max(maxValue,sum)
    
    else :
        for i in arr:
            maxValue = max(maxValue,i)
    print(maxValue)

Solution (Python):
from itertools import accumulate, combinations
while True:
    n = int(input())
    if n == 0:
        break
    L = [None]*n
    for i in range(n):
        L[i] = int(input())

    M = []
    M.append(0)
    M.extend(list(accumulate(L)))
    K = [ M[j] - M[i] for i, j in combinations(range(n+1),2)]
    print(max(K))

Solution (Python):
while True:
    n = int(input())
    if n == 0:
        break

    a = [int(input()) for i in range(n)]

    sum = [0 for i in range(n + 1)]
    for i in range(n):
        sum[i + 1] = sum[i] + a[i]

    ans = -(10**18)
    for i in range(n + 1):
        for j in range(1, i + 1):
            ans = max(ans, sum[i] - sum[i - j])

    print(ans)

Solution (Python):
"""
全探索１　O(n^3)
while 1:
    a = []
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for i in range(n)]
    max = 0
    for i in range(n):
        for j in range(i, n):
            sum = 0
            for k in range(i, j+1):
                sum += a[k]
            if max < sum:
                max = sum
    print(max)
"""
while 1:
    a = []
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for i in range(n)]
    max = -111111111111111
    for i in range(n):
        sum = 0
        for j in range(i, n):
            sum += a[j]
            if sum > max:
                max = sum

    print(max)

Solution (Python):
while 1:
 n=int(input())
 if n==0:break
 a=[int(input())for _ in[0]*n]
 for i in range(1,n):a[i]=max(a[i],a[i]+a[i-1])
 print(max(a))

Solution (Python):
def solve():
    from sys import stdin
    f_i = stdin
    
    while True:
        n = int(f_i.readline())
        if n == 0:
            break
        
        ans = int(f_i.readline())
        s = ans
        for i in range(n - 1):
            if s > 0:
                s += int(f_i.readline())
            else:
                s = int(f_i.readline())
            if s > ans:
                ans = s
        print(ans)

solve()

Solution (Python):
while True:
  n = int(input())
  if n == 0:
    break
  seq = []
  for _ in range(n):
    seq.append(int(input()))
  p_sum = -2000000
  for i in range(n):
    t_sum = 0
    for j in range(i,n):
      t_sum += seq[j]
      if t_sum > p_sum:
        p_sum = t_sum
  print(p_sum)

Solution (Python):
import sys

n = int(input())
while n != 0:
    max_seq = []
    max_val = int(input())
    for i in range(n-1):
        num = int(input())
        if num >= 0 and max_val >= 0:
            max_val += num
        else:
            if max_val >= 0:
                max_seq.append(max_val)
            if max_val >= 0 and max_val+num >= 0:
                max_val += num
            elif max_val >= 0 and max_val+num < 0:
                max_val = num
            elif max_val < 0 and max_val < num:
                max_val = num
    max_seq.append(max_val)
    print(max(max_seq))
    n = int(input())

Solution (Python):
while(1):
	n = int(input())
	if n == 0:
		break
	elif n == 1:
		print(int(input()))
	else:
		a = [0 for i in range(n+1)]
		for i in range(n):
			b = int(input())
			a[i+1] = a[i] + b
		c = [0 for i in range(n)]
		for i in range(n):
			c[i] = max(a[i+1:]) - a[i]
		print(max(c))

Solution (Python):
while True:
    n = int(input())
    if n == 0:
        break
    seq = [int(input()) for _ in range(n) ]
    for i in range(1, n):
        seq[i] = max(seq[i], seq[i - 1] + seq[i])
    print(max(seq))

Solution (Python):
while True:
    t = int(input())
    if t == 0:
        break
    tmp = [int(input()) for i in range(t)]
    res = [tmp[0]]
    for i in range(1,t):
        res.append(max(tmp[i], tmp[i]+res[i-1]))

    print(max(res))

Solution (Python):
while True:
    n = int(input())
    if n == 0: break

    a = [int(input()) for _ in range(n)]
    s = 0
    result = -1000000

    for i in range(n):
        s = 0
        for j in range(i, n):
            s += a[j]
            result = max(s, result)
    print(result)

Solution (Python):

while True:
    n = int(input())
    if n == 0: break
    a, b = 0, -100000
    num = [int(input()) for _ in range(n)]
    for n in num:
        a = max(a+n, n)
        b = max(a, b)
    print(b)

Solution (Python):
while True:
    n = int(input())
     
    if n == 0:
        break
     
    res = -1111111111
    s = 0
    for i in range(n):
        a = int(input())
        s = max(s + a, a)
        res = max(s, res)
     
    print(res)

Solution (Python):
while(True):
    n = int(input())
    if n == 0:
        break
    r = -20000005
    s = 0
    for _ in range(n):
        a = int(input())
        s = max(a+s,a)
        r = max(r,s)
    print(r)

Solution (Python):

n = int(input())
while not n == 0:
    cnd = []
    cs = 0
    for _ in range(n):
        if cs < 0 : cs = 0
        cs += int(input())
        cnd.append(cs)
    print(max(cnd))
    try: n = int(input())
    except EOFError: break