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: Runtime Error

Solution code:
import sys
while True:
    n=int(input())
    if n==0:
        sys.exit()

    sum_list=[0]
    for i in range(n):
        sum_list.append(sum_list[-1]+int(input()))

    if max(sum_list)==0:
        sum_list.pop(0)
        print(max(sum_list))
    maximum=0
    for i in range(n):
        for j in range(i,n+1):
            maximum=max(sum_list[j]-sum_list[i],maximum)

    print(maximum)

Submission status: Runtime Error

Solution code:
n=int(input())
while n!=0:
    sum_list=[0]
    for i in range(n):
        sum_list.append(sum_list[-1]+int(input()))

    if max(sum_list)==0:
        sum_list.pop(0)
        print(max(sum_list))
    maximum=0
    for i in range(n):
        for j in range(i,n+1):
            maximum=max(sum_list[j]-sum_list[i],maximum)

    print(maximum)
    n=int(input())

Submission status: Runtime Error

Solution code:
a = []
b = []


def searchs(i, n, m):
    b.clear()
    for k in range(i+1, n+1):
        b.append(sum(a[i:k]))
    # print(b)
    if m < max(b):
        m = max(b)
    if i+1 < n:
        m = searchs(i+1, n, m)
    return m


while True:
    user = input()
    n = int(user)
    if n == 0:
        break
    a.clear()
    for i in range(n):
        a.append(int(input()))
    # print(a)
    print(searchs(0, n, 0))

Submission status: Runtime Error

Solution code:
a = []
b = []


def searchs(i, n, m):
    if b != []:
        b.clear()
    for k in range(i+1, n+1):
        b.append(sum(a[i:k]))
    # print(b)
    if m < max(b):
        m = max(b)
    if i+1 < n:
        m = searchs(i+1, n, m)
    return m


while True:
    user = input()
    n = int(user)
    if n == 0:
        break
    a.clear()
    for i in range(n):
        a.append(int(input()))
    # print(a)
    print(searchs(0, n, 0))

Submission status: Runtime Error

Solution code:
a = []
b = []


def searchs(i, n, m):
    if b != []:
        b.clear()
    if a != []:
        for k in range(i+1, n+1):
            b.append(sum(a[i:k]))
    if m < max(b):
        m = max(b)
    if i+1 < n:
        m = searchs(i+1, n, m)
    return m


while True:
    user = input()
    n = int(user)
    if n == 0:
        break
    if a != []:
        a.clear()
    for i in range(n):
        a.append(int(input()))
    # print(a)
    print(searchs(0, n, 0))

Submission status: Runtime Error

Solution code:
while 1:
  n = input()
  a = []
  for i in range(n):
    k = input()
    a.append(k)
  if len(a) > 0:
    print max([sum(a[i:(j+1)]) for i in range(7) for j in range(i,7)])

Submission status: Runtime Error

Solution code:
while int(input()) != 0:
    sum=0
    for i in range(n):
         sum=sum+int(input())   
    print sum

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
n=int(input())
while n!=0:
    for i in range(n):
        list[i]=int(input())
    a=0
    b=0
    for i in range(n):
        for j in range(n-i):
            a+=list[i+j]
        if b<a:
            b=a
    print a
    n=int(input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
n=int(input())
while n!=0:
    for i in range(n):
        list[i]=int(input())
    a=0
    b=0
    for i in range(n):
        for j in range(n-i):
            a+=list[i+j]
        if b<a:
            b=a
    print a
    n=int(input()),

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
n=int(input())
while n!=0:
    for i in range(n):
        list.append(int(input()))
    a=0
    b=0
    for i in range(n):
        for j in range(n-i):
            a+=list[i+j]
        if b<a:
            b=a
    print a
    n=int(input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
n=int(raw_input())
while n!=0:
    for i in range(n):
        list.append(int(raw_input()))
    a=0
    b=0
    for i in range(n):
        for j in range(n-i):
            a+=list[i+j]
        if b<a:
            b=a
    print a
    n=int(input())

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    d = [a[0]]
    for i in range(n):
        if d[0] == 0:
            d[0] += a[i]
        elif a[i] / d[-1] >= 0:
            d[-1] += a[i]
        else:
            d.append(a[i])
    if d[0] < 0:
        d.pop(0)
    print(d)
    if len(d) <= 2:
        print(max(d))
    else:
        maxd = max(d)
        for i in range(0, len(d), 2):
            for j in range(i + 1, len(d) + 1, 2):
                print("{} {} {}".format(i, j, sum(d[i:j])))
                maxd = max(maxd, sum(d[i:j]))
        print(maxd)

Submission status: Runtime Error

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    d = [a[0]]
    for i in range(n):
        if d[0] == 0:
            d[0] += a[i]
        elif a[i] / d[-1] >= 0:
            d[-1] += a[i]
        else:
            d.append(a[i])
    if d[0] < 0:
        d.pop(0)
    if d == []:
        print(max(a))
    if len(d) <= 2:
        print(max(d))
    else:
        maxd = max(d)
        for i in range(0, len(d), 2):
            for j in range(i + 1, len(d) + 1, 2):
                maxd = max(maxd, sum(d[i:j]))
        print(maxd)

Submission status: Runtime Error

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    d = [a[0]]
    for i in range(n):
        if d[0] == 0:
            d[0] += a[i]
        elif a[i] / d[-1] >= 0:
            d[-1] += a[i]
        else:
            d.append(a[i])
            
    if len(d) <= 2:
        print(max(max(d), max(a))
    else:
        if d[0] < 0:
            d.pop(0)
        maxd = max(d)
        for i in range(0, len(d), 2):
            for j in range(i + 1, len(d) + 1, 2):
                maxd = max(maxd, sum(d[i:j]))
        print(maxd)

Submission status: Runtime Error

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:b.popleft()
    while b[-1] <= 0:b.pop()
    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: Runtime Error

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:b.popleft()
    while b[-1] <= 0 and len(b) > 1:b.pop()
    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: Runtime Error

Solution code:
def inc(x):
    return x+1
while True:
    n = int(raw_input())
    if n == 0:
        break
    numbers = [int(raw_input()) for i in range(n)]
    pointers = filter(lambda x:x[0]<x[1], map(lambda x:(x/n,x%n+1),xrange(n*n)))
    ans = 0
    for pointer in pointers:
        tmp = reduce(lambda x,y:x+y,numbers[pointer[0],pointer[1]])
        ans = tmp > ans if tmp else ans
    print ans

Submission status: Runtime Error

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:
        return max(numbers)
    ans = 0
    for i in range(n):
        tmp = 0
        for j in range(i,n):
            tmp += numbers[j]
            ans = max(ans,tmp)
    print ans

Submission status: Runtime Error

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

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

    tup = tuple(int(stdin.readline()) for _ in xrange(n))
    L = [tup[0]]
    for i in tup[1:]:
        if 0 > i and 0 > L[-1]:
            L[-1] += i
        elif 0 <= i and 0 <= L[-1]:
            L[-1] += i
        else:
            L.append(i)

    while True:
        length = len(L)
        if L[0] <= 0:
            L.pop(0)
            continue
        if L[-1] <= 0:
            L.pop()
            continue
        if length > 1 and L[0] + L[1] <= 0:
            L.pop(0)
            L.pop(0)
            continue
        if length > 1 and L[-1] + L[-2] <= 0:
            L.pop()
            L.pop()
            continue
        if length > 2 and sum(L[:3]) >= L[2]:
            L[2] = sum(L[:3])
            L.pop(0)
            L.pop(0)
            continue
        if length > 2 and sum(L[-3:]) >= L[-3]:
            L[-3] = sum(L[-3:])
            L.pop(0)
            L.pop(0)
            continue
        break

    m = 0
    for i in xrange(len(L)):
        for j in xrange(1 + i, len(L) + 1):
            t = sum(L[i:j])
            if t > m:
                m = t
    print(m)

Submission status: Runtime Error

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

def grouping(nums):
    it = iter(nums)
    L = [next(nums)]
    minus = L[0] < 0
    for n in it:
        if (n < 0 and minus) or (n >= 0 and not minus):
            L[-1] += n
        else:
            L.append(n)
            minus = not minus
    return L

def collect(nl):
    result = 0
    while len(nl) > 1:
        nl = grouping(nl[i] + nl[i+1] for i in xrange(0, len(nl), 2))
        if nl[-1] <= 0:
            nl.pop()
            if not len(nl):
                break
        if nl[0] >= 0:
            result += nl[0]
            nl.pop(0)
    return result

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

    L = grouping(int(stdin.readline()) for _ in xrange(n))
    if L[0] <= 0:
        L.pop(0)
    if L[-1] <= 0:
        L.pop()

    val = max(L)
    idx = L.index(val)

    val += collect(list(reversed(L[:idx])))
    val += collect(L[idx+1:])
    print(val)

Submission status: Runtime Error

Solution code:
while True:
	n = input()
	if n == 0:
		break
	else:
		nums = []
		for val in range(1,n+1):
			nums.append(input())
		sums = []
		for val in range(0,n):
			sums.append(nums[val]+nums[val+1])
		sums.sort()
		sums.reverse()
		print sums[0]
		continue

Submission status: Runtime Error

Solution code:
while True:
	n = input()
	if n == 0:
		break
	else:
		nums = []
		for val in range(1,n+1):
			num = int(raw_input())
			nums.append(num)
		sums = []
		for val in range(0,n-1):
			sums.append(nums[val]+nums[val+1])
		sums.sort()
		sums.reverse()
		print sums[0]
		continue

Submission status: Runtime Error

Solution code:
while True:
	n = input()
	if n == 0:
		break
	else:
		nums = []
		for val in range(1,n+1):
			num = int(raw_input())
			nums.append(num)
		sums = []
		for val in range(1,n):
			sums.append(nums[val-1]+nums[val])
		sums.sort()
		sums.reverse()
		print sums[0]
		continue

Submission status: Runtime Error

Solution code:

import sys


def max_sum_seq(lis):
    r = []
    l = len(lis)
    for n in range(1, l+1):
        r = r + every_slice(lis, n)
    return max(map((lambda r1: reduce((lambda x, y: x + y), r1, 0)), r))

def every_slice(lis, n):
    r = []
    l = len(lis)
    for i in range(l-n+1):
        r.append(lis[i:i+n])
    return r


#input_file = open(sys.argv[1], "r")

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

Submission status: Runtime Error

Solution code:
----:---F1  *scratch*      All L1     (Fundamental)------------------------------------------------------------------------------------
Loading subst-jis...done
while True:
    n =	int(raw_input())
    if n == 0:
	break
    a=[]
    for i in range(n):
	a[i] = int(raw_input())
    max	= -1e10
    for	i in range(len(a)):
	sum = 0
        for j in range(i+1:len(a)):
	    sum += a[j]
      	    if sum > max:
		max = sum
    print max