Problem:


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.

Input

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.

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



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


Sample output:
19
14
1001

Submission status: Accepted

Solution code:
while True:
    n = int(input())

    if n == 0:
        break

    dp = []

    for _ in range(n):
        if len(dp) == 0:
            dp.append(int(input()))
        else:
            x = int(input())
            dp.append(max(dp[-1] + x, x))

    print(max(dp))

Submission status: Accepted

Solution code:
while(1):
    a=[]
    n = int(input())
    if n==0:
        break
    a=[int(input()) for i in range(n)]
    result=[]
    for i in range(n):
        result1=a[i]
        result.append(result1)
        for j in range(i+1,n):
            result1=result1+a[j]
            result.append(result1)
    print(max(result))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
while True:
    n = int(raw_input())
    if n != 0:
        max = -9999999999999
        a =[int(raw_input()) for i in range(n)]
        #print a
        for j in range(0,n):
            sum = 0
            for k in range(0,n-j):
                sum += a[k+j]
                if sum > max:
                    max = sum
        print max
    else:
        break

Submission status: Accepted

Solution code:
import math

def sign(x):
    if x >= 0:
        return True
    else:
        return False

n = int(input())
while n != 0:
    a = []
    for i in range(n):
        a.append(int(input()))
    b = []
    b.append(a[0])
    for i in range(1,len(a)):
        if b[len(b)-1] > 0 and a[i] > 0:
            b[len(b)-1] = b[len(b)-1] + a[i]
        else:
            b.append(a[i])

    ans = b[0]
    for i in range(len(b)):
        S = 0
        for j in range(i,len(b)):
            S = S + b[j]
            ans = max(S, ans)
    print(ans)
    n = int(input())

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        quit()
    a = []
    for i in range(n):
        a.append(int(input()))
    mn = -100001
    for i in range(len(a)):
        temp = a[i]
        mn = max(mn, temp)
        for j in range(i+1, len(a)):
            temp += a[j]
            mn = max(mn, temp)
    print(mn)

Submission status: Accepted

Solution code:
while 1:
	n=int(input())
	if n==0: break
	a=[int(input()) for i in range(n)]
	temp = 0
	most = -999999999
	for i in range(n):
		temp = 0
		for j in range(i,n):
			temp +=	a[j]
			if temp > most:
				most = temp
	print(most)

Submission status: Accepted

Solution code:
while True:
    n=int(input())
    if n==0:break
    l=[int(input()) for i in range(n)]
    s=0
    m=0
    for li in l:
        s=max(0,s+li)
        m=max(m,s)
    print(m if m else max(l))

Submission status: Accepted

Solution code:
while(1):
    N = int(input())
    if N==0: break
    sums = []
    nums = []
    s = 0
    for i in range(N):
        n = int(input())
        nums.append(n)
        s += n
        if s<0: s=0
        sums.append(s)
    if max(nums) >= 0:
        print(max(sums))
    else:
        print(max(nums))

Submission status: Accepted

Solution code:
INF = 10 ** 20
while True:
  n = int(input())
  if not n:
    break
  cum_sum = [0]
  acc = 0
  for i in range(n):
    acc += int(input())
    cum_sum.append(acc)
  ans = -INF
  for i in range(n):
    ans = max(ans, max(cum_sum[i + 1:]) - cum_sum[i])
  print(ans)

Submission status: Accepted

Solution code:
from collections import deque
while True:
    n = int(input())
    if n == 0:break
    a = [int(input()) for _ in range(n)]
    b = deque([0] * n)
    j = 0
    for i in range(n):
        if a[i] * b[j] >= 0:b[j] += a[i]
        else:j += 1;b[j] += a[i]
    if b[0] < 0 and len(b) > 1:b.popleft()
    while b[-1] <= 0 and len(b) > 1:b.pop()
    if len(b) == 1 and b[0] <= 0:print(max(a))
    else:
        m = len(b) // 2 + 1
        v = [[0] * m for _ in range(m)]
        v[0][0] = b[0]
        for i in range(1, m):
            v[0][i] = v[0][i - 1] + b[2 * i] + b[2 * i - 1]
        for i in range(1, m):
            for j in range(i, m):
                v[i][j] = v[i - 1][j] - b[2 * i - 2] - b[2 * i - 1]
        print(max([max(i) for i in v]))

Submission status: Accepted

Solution code:
# AOJ 0022 Maximum Sum Sequence
# Python3 2018.6.16 bal4u

while 1:
	n = int(input())
	if n == 0: break
	s = [0]*5001
	ans = s[0] = int(input())
	for i in range(1, n):
		v = int(input())
		s[i] = v if s[i-1]+v < v else s[i-1]+v
		if s[i] > ans: ans = s[i]
	print(ans)

Submission status: Accepted

Solution code:
while 1:
    n=int(input())
    if not n:break
    dp=[0 for _ in range(n)]
    dp[0]=int(input())
    for i in range(1,n):
        v=int(input())
        dp[i]=max(dp[i-1]+v,v)
    print(max(dp))

Submission status: Accepted

Solution code:
def max_sub(array):
    x = max(array[0], 0)
    ans = 0
    for a in array[1:]:
        x = max(0, x+a)
        ans = max(ans, x)
    return ans

while True:
    n = int(input())
    if n == 0:
        break
    array = [int(input()) for _ in range(n)]
    ans = max_sub(array)
    ans = max(array) if ans <= 0 else ans
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
#-*- coding:utf-8 -*-
while True:
	n = input()
	if n == 0: break
	a = [ input() for i in xrange(n) ]
	m = -100000
	for i in xrange(n):
		s = 0
		for j in xrange(i, n):
			s += a[j]
			m = max(m, s)
	print m

Submission status: Accepted

Solution code:
while 1:
    n=input()
    if(n==0):break
    a=[]
    for i in range(n):
        a.append(input())
    s=[0]
    for i in range(n):
        s.append(s[-1]+a[i])
    ans=-100001
    for i in range(n):
        for j in range(i+1,n+1):
            ans=max(ans,s[j]-s[i])
    print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

def solve():
    while True:
        n = input()
        if n > 0:
            tmp_lst = []
            for i in xrange(n):
                tmp_lst.append(input())
            lst = compress(tmp_lst)
            accumurate_lst = calc_accumurate_lst(lst)
            max_value = - (10 ** 100)
            size = len(lst)
            for to in xrange(size):
                for frm in xrange(to + 1):
                    value = accumurate_lst[to] if frm == 0 else accumurate_lst[to] - accumurate_lst[frm - 1]
                    if max_value < value:
                        max_value = value
            print max_value
        else:
            sys.exit()

def calc_accumurate_lst(lst):
    accum = [0 for i in lst]
    accum[0] = lst[0]
    for i in xrange(1, len(lst)):
        accum[i] = accum[i - 1] + lst[i]
    return accum
        
#同じ符号の数列は圧縮できる
def compress(tmp_lst):
    lim = len(tmp_lst)
    #リスト圧縮
    lst = []
    index = 0
    while index < lim:
        tmp = tmp_lst[index]
        index += 1
        while tmp > 0 and index < lim and tmp * tmp_lst[index] > 0:
            tmp += tmp_lst[index]
            index += 1
        lst.append(tmp)
    return lst

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
while True:
    n=input()
    if n == 0: break
    a=[input() for i in range(n)]
    m=max(a)
    if m<=0: print m
    else:
        ans,temp=0,0
        for i in a:
            temp=max(0,temp+i)
            ans=max(ans,temp)
        print ans
#temp

Submission status: Accepted

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    numbers = [int(raw_input()) for i in range(n)]
    if max(numbers) <= 0:
        print max(numbers)
    else:
        ans = 0
        for i in range(n):
            tmp = 0
            for j in range(i,n):
                tmp += numbers[j]
                if(ans<tmp):
                    ans = tmp
        print ans

Submission status: Accepted

Solution code:
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from array import array

def grouping(nums):
    sign = None
    L = array(b'i')
    for s, n in ((i < 0, i) for i in nums):
        if sign is s:
            L[-1] += n
        else:
            sign = s
            L.append(n)

    if len(L) and L[-1] <= 0:
        del L[-1]
    if len(L) and L[0] <= 0:
        del L[0]
    return L

while True:
    n = int(stdin.readline())
    if not n:
        break

    L = array(b'i', (int(stdin.readline()) for _ in xrange(n)))
    val = max(L)
    if val <= 0:
        print(val)
        continue

    ans, temp = 0, 0
    for i in grouping(L):
        temp = max(0, temp+i)
        ans = max(ans, temp)
    print(ans)

Submission status: Accepted

Solution code:

import sys


def max_sum_seq(lis):
    m = 0
    lis = compress(lis)
    l = len(lis)

    max_val = lis[0]
    for i in xrange(0, l):
        for j in xrange(i, l):
            if j == i:
                tmp_val = lis[j]
            else:
                tmp_val = tmp_val + lis[j]
            max_val = max(max_val, tmp_val)
    return max_val

def compress(tmp_lst):
    lim = len(tmp_lst)
    lst = []
    index = 0
    while index < lim:
        tmp = tmp_lst[index]
        index += 1
        while tmp > 0 and index < lim and tmp * tmp_lst[index] > 0:
            tmp += tmp_lst[index]
            index += 1
        lst.append(tmp)
    return lst


while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    lis = []
    for i in range(n):
        lis.append(int(sys.stdin.readline()))
    print max_sum_seq(lis)

Submission status: Accepted

Solution code:
while True:
    n = input()
    if n==0: break
    s = None
    x = []
    for i in range(n):
        n1=input()
        x=[e+n1 for e in x]+[n1]
        if n>0 or s==None:
            s=max(max(x),s)
    print s

Submission status: Accepted

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    a = [0] * n
    dp = [0] * n
    for i in range(n):
        a[i] = int(raw_input())
        if i == 0:
            dp[0] = a[0]
        else:
            dp[i] = max(dp[i-1]+a[i], a[i])
    print max(dp)

Submission status: Accepted

Solution code:
#!/usr/bin/python


def main():
    while True:
        try:
            num_data = int(raw_input())
            if num_data == 0:
                break

            data = []
            for i in xrange(num_data):
                data.append(int(raw_input()))

            max = max_sum_sequence(data)
            print(max)
        except:
            break


def max_sum_sequence(data):
    sum = [0]
    n = len(data)

    for i in xrange(n):
        sum.append(sum[-1] + data[i])

    mx = - (1 << 30)
    for i in xrange(n):
        for j in xrange(i + 1, n + 1):
            mx = max(mx, sum[j] - sum[i])

    return mx


main()

Submission status: Accepted

Solution code:
n=input()
while n:
    R=[input() for i in range(n)]
    x=R
    s=max(x)
    while n-1:
        R=R[1:]
        x=[a+b for a,b in zip(x[:-1],R)]
        s=max(s,max(x))
        n-=1
    print s
    n=input()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
def maximumSubArray(array):
    n = len(array)
    dp = [0]*n # dp[i]: i番目までの全ての部分配列の中の最大の総和
    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))

Submission status: Accepted

Solution code:
# INF = float("inf")
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]
   #print(a)
   for i in range(1,n):
     ml = max(ml+a[i],a[i])
     mg = max(mg,ml)
     #print(ml,mg,a[i])
   print(mg)

Submission status: Accepted

Solution code:
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():
    ...

Submission status: Accepted

Solution code:
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:
            # 合計が0以下になってしまった場合はこれ以上計算しても意味がないのでスルーする
            if sum > 0:
                # plusが連続して続いていた場合
                if(isPlus):
                    # 最大値を更新
                    maxValue = max(maxValue,sum)
                    isPlus = False
                sum += arr[i]
                # 0未満になったら、1から計算し直す
                if sum < 0 :
                    sum = 0
        else :
            sum += arr[i]
            isPlus = True
    if sum != 0 :
        maxValue = max(maxValue,sum)
    # 入力値が全てminusなので、入力値から最大のものを探す    
    else :
        for i in arr:
            maxValue = max(maxValue,i)
    print(maxValue)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
"""
全探索１　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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# Maximum Sum Sequence
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

Submission status: Output Limit Exceeded

Solution code:
while 1:
	n=input()
	if n==0:break
	r=[input()for i in xrange(n)]
	print r
	for i in xrange(1,n):
		r[i]=max(r[i-1]+r[i],r[i])
		print r
	print max(r)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

lis = []
lis2 = []

def sum(lis):
  s = 0
  for e in lis:
    s += e
  return s

while True:
  num = input()
  if num == 0:
    break
  else:
    lis = []
    lis2 = []
    for i in range(num):
      n = input()
      if i == 0:
        d = n
      else:
        d = max( d + n , n )
        lis.append(d)    
    print max(lis)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

lis = []
lis2 = []


while True:
  num = input()
  if num == 0:
    break
  else:
    lis = []
    for i in range(num):
      n = input()
      if i == 0:
        d = n
      else:
        d = max( d + n , n )
        lis.append(d)    
    print max(lis)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
  num = input()
  if num == 0:
    break
  lis = []
  for i in range(num):
    n = input()
    if i == 0:
      d = n
    else:
      d = max( d + n , n )
      lis.append(d)    
  print max(lis)

Submission status: Runtime Error

Solution code:
while True:
    n=int(input())
    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))

Submission status: Runtime Error

Solution code:
while 1:
    n = int(input())
    a = [int(input()) for _ in range(n)]

    dp = [a[0]]
    for i in range(1,len(a)):
        dp.append(max(dp[i-1] + a[i], a[i]))

    print(max(dp))

Submission status: Runtime Error

Solution code:
while 1:
    n = int(input())
    a = []
    for _ in range(n):
        a.append(int(input()))

    dp = [a[0]]
    for i in range(1,len(a)):
        dp.append(max(dp[i-1] + a[i], a[i]))

    print(max(dp))

Submission status: Runtime Error

Solution code:
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()))

Submission status: Runtime Error

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    dp = [0]
    for i in range(n):
        a = int(input()))
        dp[i] = (max(dp[i] + a, a))
    print(max(dp))

Submission status: Runtime Error

Solution code:
while True:
	n=int(input())
	if n==0:
		break
	A=[]
	for i in range(n):
		A.append(int(input()))
	start=0
	for i in A:
		if i<=0:
			start+=1
		else:
			break
	B=A[start:]
	end=len(B)
	MAX=[0]*end
	for i in range(end):
		for j in range(i+1,end+1):
			s=sum(B[i:j])
			if MAX[i]<s:
				MAX[i]=s
	print(max(MAX))

Submission status: Runtime Error

Solution code:
while True:
	n=int(input())
	if n==0:
		break
	A=[]
	for i in range(n):
		A.append(int(input()))
	start=0
	for i in A:
		if i<=0:
			start+=1
		else:
			break
	B=A[start:len(A)+1]
	end=len(B)
	MAX=[0]*end
	for i in range(end):
		for j in range(i+1,end+1):
			s=sum(B[i:j])
			if MAX[i]<s:
				MAX[i]=s
	print(max(MAX))

Submission status: Runtime Error

Solution code:
#! -*-coding:utf-8-*-

def signCheck(argn):
    if argn>0:
        return 1
    elif argn==0:
        return 1
    else:
        return -1

def maxSumSequence(nums):
    pluslist=[]
    minuslist=[]
    prenum = 0
    presign=signCheck(nums[0])
    begin=presign
    nsum=0
    for num in nums:
        nowsign=signCheck(num)
        if nowsign>0:
            if presign==nowsign:
                nsum+=num
            else:
                minuslist.append(nsum)
                nsum=num
        #?¬?????????????????????????????????????
        else:
            if presign==nowsign:
                nsum+=num
            else:
                pluslist.append(nsum)
                nsum=num
        presign=nowsign
    if nowsign>0:
        pluslist.append(nsum)
    else:
        minuslist.append(nsum)

    if begin<0:
        del minuslist[0]
    if nowsign<0:
        minuslist[-1]=0
    sumlist=[]
    sumlist.append(pluslist[0])
    del pluslist[0]
    for pnum,mnum in zip(pluslist,minuslist):
        sumlist.append(pnum+mnum)
    return sumlist

def main():
    while True:
        n=input()
        if n==0:
            break
        nums = []
        for i in xrange(n):
            nums.append(input())
        while len(nums)>1:
            nums = maxSumSequence(nums)
        print nums[0]

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

import sys

while True:
	x = input()
	num, ans = [], []
	if x == 0: break
	else:
		for j in xrange(x):
			num.append(input())
		for j in xrange(x):
			if num[j] > 0:
				for k in xrange(j + 1,x + 1):
# 					print num[j:k]
# 					print sum(num[j:k])
 					ans.append(sum(num[j:k]))
			else:
				pass
		print max(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    b = []
    while a != []:
        for i in range(len(a) - 1):
            if a[i] * a[i + 1] < 0:
                b.append(sum(a[:i + 1]))
                a[:i + 1] = []
                break
        else:
            b.append(sum(a))
            a = []
    for i in range(1, len(b)):
        if b[i - 1] > 0:
            b[i] += b[i - 1]
    print(max(b)

Submission status: Runtime Error

Solution code:
while 1:
    n = input()
    if n == 0: break
    sums = []
    a, b, c = 0, 0, input()
    for i in xrange(n - 1):
        sums.append(a + b + c)
        a, b, c = b, c, input()
    print max(sums)

Submission status: Runtime Error

Solution code:
while True:
    n = input()
    if n == 0:
        exit()
    A = [int(raw_input()) for _ in xrange(n)]
    if all(a<=0 for a in A):
        print max(a)
        exit()
    
    r = 0
    tmp = 0
    ans = 0
    while r < n:
        tmp += A[r]
        if tmp < 0:
            l = r
            tmp = 0
        else:
            ans = max(ans, tmp)
        r += 1
    print ans

Submission status: Runtime Error

Solution code:
while True:
 try:
  n=int(input())
  a=[int(input()) for i in range(n)]
  print(max(a))
 except EOFError:
  break

Submission status: Runtime Error

Solution code:
while 1:
    n = int(raw_input())
    max = 0
    for i in range(n):
        tmax = max + int(raw_input())
        if tmax > max:
            max = tmax
    print tmax

Submission status: Runtime Error

Solution code:
def solve(v):
    w = []
    sig=sign(v[0])
    x = v[0]    
    for i in range(1,len(v)):
        if v[i] * sig >= 0:
            x += v[i]
        else:
            w.append(x)
            sig=sign(v[i])
            x=v[i]
    w.append(x)
#    print(w)
    return(solve0(w))      

if __name__ == "__main__":
    while True:
        n = int(input())
        if n == 0:
            break
        v = []    
        for i in range(n):
            v.append(int(input()))

        print(solve(v))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

N = int(input())

for i in range(N):
    ax, ay, ar, bx, by, br = map(float, input().split())

    between_center = math.hypot(ax - bx, ay - by)

    # ????????£????????????
    if between_center > ar + br:
        print(0)

    # ????????????????????¨
    else:
        # B in A
        if ar > between_center + br:
            print(2)

        # A in B
        elif br > between_center + ar:
            print(-2)

        else:
            print(1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math


N = int(input())

for i in range(N):
    ax, ay, ar, bx, by, br = map(float, input().split())

    between_center = math.hypot(ax - bx, ay - by)

    # ????????£????????????
    if between_center > ar + br:
        print(0)

    # ????????????????????¨
    else:
        # B in A
        if ar > between_center + br:
            print(2)

        # A in B
        elif br > between_center + ar:
            print(-2)

        else:
            print(1)

Submission status: Runtime Error

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break

    a = (int(raw_input()) for _ in xrange(n))
    b = []
    c = 0
    for ai in a:
        if ai == 0:
            continue
        if (c > 0 and ai < 0) or (c < 0 and ai > 0):
            b.append(c)
            c = 0
        c += ai

    if c != 0:
        b.append(c)

    l = len(b)
    i = 0 if b[0] > 0 else 1
    s = b[i]
    ans = s

    j = i + 2
    while j < l:
        s += b[j - 1] + b[j]
        while i < j:
            ns = s - b[i] - b[i + 1]
            if ns < s:
                break
            s = ns
            i += 2
        ans = max(s, ans)
        j += 2

    print(ans)