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: Time Limit Exceeded

Solution code:

import sys


def max_sum_seq(lis):
#    r = []
    m = 0
    l = len(lis)
    for n in range(1, l+1):
        for s in every_slice(lis, n):
            sm = sum(s)
            if sm > m:
                m = sm
    return m
#        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):
        yield lis[i:i+n]
#    return r


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

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: Time Limit Exceeded

Solution code:

import sys


def max_sum_seq(lis):
    m = 0
    l = len(lis)
    for n in range(1, l+1):
        for s in every_slice(lis, n):
            sm = sum(s)
            if sm > m:
                m = sm
    return m

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


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: Time Limit Exceeded

Solution code:

import sys


def max_sum_seq(lis):
    m = 0
    lis = compress(lis)
    l = len(lis)
    for n in range(1, l+1):
        for s in every_slice(lis, n):
            sm = sum(s)
            if sm > m:
                m = sm
    return m

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

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: Time Limit Exceeded

Solution code:
while True:
    n = input()
    if n==0: break
    s=[]
    x=[]
    for i in range(n):
        x.append(input())
    for i in range(n):
        for j in range(i,n):
            s.append(sum(x[i:j+1]))
    print max(s)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


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

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

        print(max_sum_sequence(data))


def max_sum_sequence(data):
    max = 0
    num_data = len(data)
    for l in xrange(num_data + 1):
        sum = max_at_length(data, l)
        if sum > max:
            max = sum

    return max


def max_at_length(data, length):
    max = 0
    num_data = len(data)
    for begin in xrange(num_data):
        sum = 0
        for i in xrange(begin, begin + length):
            if i >= num_data:
                continue

            sum += data[i]

        if sum > max:
            max = sum

    return max


main()

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
ans = []
while n > 0:
  a = []
  for i in range(n):
    a.append(int(raw_input()))
  max_sum = -100000*len(a)
  for i in range(len(a)):
    for j in range(i+1, len(a)):
      part_sum = sum(a[i:j])
      if part_sum > max_sum: max_sum = part_sum
  print max_sum
  n = int(raw_input())

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
ans = []
while n > 0:
  a = []
  for i in range(n):
    a.append(int(raw_input()))
  len_a = len(a)
  max_sum = -100000*len_a
  for i in range(len_a + 1):
    for j in range(i+1, len_a + 1):
      part_sum = sum(a[i:j])
      if part_sum > max_sum: max_sum = part_sum
  print max_sum
  n = int(raw_input())

Submission status: Memory Limit Exceeded

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

import os
import sys

class Hoge(object):
    
    def __init__(self):
        pass

    def func(self):
        '''
        insert your code
        '''
        while True:
            n = input()
            if n == 0:
                break
            num = [input() for i in range(n)]
            s = [[0 for i in range(5001)] for j in range(5001)]
            for i in range(n):
                s[i][0] = num[i]
                for j in range(1, n-i):
                    s[i][j] += s[i][j-1] + num[i+j]
            # for i in range(10):
            #     for j in range(10):
            #         print s[i][j]
            #     print
            m = -float('inf')
            for i in range(n):
                for j in range(n):
                    m = max(m, s[i][j])

            print m
        return None

if __name__ == '__main__':
    h = Hoge()
    h.func()

Submission status: Memory Limit Exceeded

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

import os
import sys

class Hoge(object):
    
    def __init__(self):
        pass

    def func(self):
        '''
        insert your code
        '''
        while True:
            n = input()
            if n == 0:
                break
            num = [input() for i in range(n)]
            s = [[-float('inf') for i in range(n+1)] for j in range(n+1)]
            for i in range(n):
                s[i][0] = num[i]
                for j in range(1, n-i):
                    s[i][j] += s[i][j-1] + num[i+j]
            # for i in range(10):
            #     for j in range(10):
            #         print s[i][j]
            #     print
            m = -float('inf')
            for i in range(n):
                for j in range(n):
                    m = max(m, s[i][j])

            print m
        return None

if __name__ == '__main__':
    h = Hoge()
    h.func()

Submission status: Memory Limit Exceeded

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)]
    if max(numbers) <= 0:
        print max(numbers)
    else:
        pointers = filter(lambda x:x[0]<x[1], map(lambda x:(x/n,x%n+1),xrange(n*n)))
        print max(map(lambda x:reduce(lambda y,z:y+z,numbers[x[0]:x[1]]),pointers))

Submission status: Memory Limit Exceeded

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)]
    if max(numbers) <= 0:
        print max(numbers)
    else:
        print max(map(lambda x:reduce(lambda y,z:y+z,numbers[x[0]:x[1]]),filter(lambda x:x[0]<x[1], map(lambda x:(x/n,x%n+1),xrange(n*n)))))

Submission status: Memory Limit Exceeded

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: Memory Limit Exceeded

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
        del pointer
    print ans
    del numbers
    del pointers

Submission status: Memory Limit Exceeded

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(sys.stdin.readline()))
    print max_sum_seq(lis)

Submission status: Accepted

Solution code:
while 1:
    n=int(input())
    if n==0:break
    nlist=[]
    nans=-100001
    for i in range(n):
        nlist.append(int(input()))
    nkeep=0
    for i in nlist:
        if nkeep<0:
            nkeep=i
        else:
            nkeep+=i
        if nans<nkeep:nans=nkeep
    if max(nlist)<0:nans=max(nlist)
    print(nans)

Submission status: Accepted

Solution code:
while True:
    N=int(input())
    
    if N==0:
        break
    
    num=0
    res=-11111111
    for i in range(N):
        a=int(input())
        num=max(num+a, a)
        #print(num)
        res=max(num, res)
        #print(res)

    print(res)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    a=[]
    for i in range(n):
        a.append(int(raw_input()))
    max = -1e10
    for i in range(len(a)):
        sum = 0
        for j in range(i,len(a)):
            sum += a[j]
            if sum > max:
                max = sum
    print max

Submission status: Accepted

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

while True:
    n = int(input())
    if n == 0:
        break
    a = []
    for i in range(0,n):
        a.append(int(input()))
    sumMax = -100000
    for i in range(0,n):
        tmp = 0
        for j in range(i,n):
            tmp += a[j]
            sumMax = max(sumMax,tmp)
    print(sumMax)

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:
import sys
f = sys.stdin

while True:
    n = int(f.readline())
    if n == 0:
        break
    a = [int(f.readline()) for i in range(n)]
    sum_max = now = 0
    for ai in a:
        now = max(0, now + ai)
        sum_max = max(sum_max, now)
    print(sum_max if sum_max else max(a))

Submission status: Accepted

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

    ans=-1e100
    l=[]

    for _ in range(n):
        l.append(int(input()))
    for i in range(n):
        s=0
        for j in range(i,n):
            s+=l[j]
            if ans < s: ans = s
    print(ans)

Submission status: Accepted

Solution code:
while True:
    sequence = []
    n = input()
    if n ==0:
        break
    for i in range(n):
        sequence.append(int(raw_input()))
    max_sum=-100000
    sum=0
    while len(sequence)!=0:
            sum+=sequence.pop(0)
            if max_sum<sum:
                max_sum=sum
            if sum<0:
                sum=0

    print max_sum

Submission status: Accepted

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

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

    m = -100000 * 5000
    for i in range(0, n):
        for j in range(i + 1, n + 1):
            m = max(m, s[j] - s[i])

    print(m)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
while 1:
	n=input()
	if n==0:break
	m=0
	r=[-10**5]*n
	for x in[input()for i in range(n)]:
		m=max(m,0)+x
		r.append(m)
	print max(r)

Submission status: Accepted

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

Submission status: Accepted

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: Accepted

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

Submission status: Accepted

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

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

    print(max(dp))

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(raw_input())
    if N == 0:
        break
    L = map(int, [raw_input() for _ in range(N)])
    
    maxi = max(L)

    for i in range(N):
        if L[i] <= 0:
            continue

        tot = L[i]
        for j in range(1, N - i):
            tot += L[i + j]

            if tot > maxi:
                maxi = tot

    print maxi

Submission status: Accepted

Solution code:
while 1:
    n=int(raw_input())
    if n==0:
        break
    a,dp=[],[]
    for i in range(n):
        a.append(int(raw_input()))
    ans=a[0]
    for i in range(n):
        tmp=0
        for j in range(i,n):
            tmp+=a[j]
            ans=max(ans,tmp)
    print ans

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  a = 0
  max_c = -200000
  while n > 0:
    i = int(input())
    a += i
    if max_c < a:
      max_c = a
    if a <= 0:
      a = 0
    n -= 1
  print(max_c)

Submission status: Accepted

Solution code:
from math import *
PI = 3.1415926535898
while True:
	try:
		n = input()
		if n == 0:
			break
		res = []
		arr = []
		su = 0
		for i in range(n):
			arr.append(input())
		res.append(arr[0])
		ans = arr[0]
		for i in range(1, n):
			res.append(max(res[i-1] + arr[i], arr[i]))
			ans = max(ans, res[i])
		print ans
	except EOFError:
		break

Submission status: Accepted

Solution code:
while True:
    num = int(input())
    if not num: break
    result, tmp = -1e6, 0
    for _ in range(num):
        new = int(input())
        tmp = max(new, new+tmp)
        result = max(tmp, result)
    print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

while True:
    n = int(input())
    if n == 0:
        break
    else:
        a = [int(input()) for i in range(n)]
        a = list(itertools.accumulate(a))
        a.insert(0, 0)
        ans = -100000
        for j in range(n):
            for k in range(j + 1, n + 1):
                ans = max(ans, a[k] - a[j])
        print(ans)

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    else:
        a = [int(input()) for i in range(n)]
        for i in range(1, n):
            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
    dp = [-1e6]
    for i in range(n):
        a = int(input())
        dp.append(max(dp[i] + a, a))
    print(max(dp))

Submission status: Accepted

Solution code:
while True:
	n=int(input())
	if n==0:
		break
	A=[]
	for i in range(n):
		x=int(input())
		A.append(x)

	B=[int()]*n
	B[0]=A[0]
	for i in range(1,n):
		if A[i]>=A[i]+B[i-1]:
			B[i]=A[i]
		else:
			B[i]=A[i]+B[i-1]
	print(max(B))

Submission status: Accepted

Solution code:
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:
# -*- coding: utf-8 -*-

while True:
    n = int(raw_input())
    if n == 0:
        break
    A = [int(raw_input()) for i in range(n)]
    sum = [[0 for i in range(n)] for j in range(n)]
    sum[0][0] = Max = A[0]
    for i in range(1, n):
        sum[0][i] = sum[0][i-1] + A[i]
        Max = max(Max, sum[0][i])
    for i in range(1, n):
        for j in range(i, n):
            sum[i][j] = sum[i][j-1] + A[j]
            Max = max(Max, sum[i][j])
    print Max

Submission status: Accepted

Solution code:
def maxsum(A):
    smax = A[0]
    ssum = max(A[0], 0)
    for a in A[1:]:
        ssum += a
        smax = max(ssum, smax)
        ssum = max(ssum, 0)
    return smax

while True:
    n = int(input())
    if not n:
        break

    A = []
    for i in range(n):
        a = int(input())
        A.append(a)

    print(maxsum(A))

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0:
        break

    m = [None] * n
    t = [None] * n
    for i in range(n):
        a = int(input())
        m[i] =  t[i] = a
        for j in range(i):
            t[j] += a
            m[j] = max(m[j], t[j])

    print(max(m))

Submission status: Accepted

Solution code:
import sys

for i in sys.stdin:
    n = int(i)
    if n == 0:
        break
    max = -100000
    sum = int(input())
    for i in range(n-1):
        m = int(input())
        if sum < 0 and sum < m:
            sum = m
        elif m < 0 and max < sum:
            max = sum
            sum += m
        else:
            sum += m
    if sum > max:
        max = sum
    print(max)

Submission status: Accepted

Solution code:
import sys

s = ""
for i in sys.stdin:
    n = int(i)
    if n == 0:
        break
    max = -100000
    sum = int(input())
    for i in range(n-1):
        m = int(input())
        if sum < 0 and sum < m:
            sum = m
        else:
            if m < 0 and max < sum:
                max = sum
            sum += m
    if sum > max:
        s += str(sum) + "\n"
    else:
        s += str(max) + "\n"

print(s,end="")

Submission status: Accepted

Solution code:
while 1:
    n=input()
    if n==0:break
    a=[int(raw_input()) for _ in xrange(n)]
    wa=[0]*(n+1)
    max_a=-1000000
    for i in xrange(n):
        wa[i+1]=a[i]+wa[i]
    for i in xrange(n):
        for j in xrange(i+1,n+1):
            if max_a<wa[j]-wa[i]:
                max_a=wa[j]-wa[i]
    print(max_a)

Submission status: Accepted

Solution code:
while True:
	n = int(input())
	if n == 0: break
	l = []
	for _ in range(n):
		l.append(int(input()))

	sum = 0
	sums = [0]
	for i in range(n):
		sum += l[i]
		sums.append(sum)

	maximum_sum = -99999999999999
	for e in range(1, n+1):
		for s in range(1, e+1):
			sum = sums[e] - sums[s-1]
			if maximum_sum < sum:
				maximum_sum = sum

	print(maximum_sum)

Submission status: Accepted

Solution code:
import itertools
while True:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    a[:0] = [0]
    for i in range(1, len(a)):
        a[i] += a[i - 1]
    print(max(map(lambda x:x[1] - x[0], itertools.combinations(a, 2))))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
while True:
    N = int(input())
    if N == 0:
        break
    A = [int(input()) for i in range(N)]
    ans = A [0]
    cur = 0
    for i in A:
        cur = max(cur + i,i)
        ans = max(ans,cur)
    print(ans)

Submission status: Accepted

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)
        continue
    
    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: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0:
        break

    ans = -1000000000
    a = [0]
    for i in range(n):
        a.append(int(input())) # a = [input() for i in range(n)]
        a[i+1] += a[i]
        
        for j in range(0,i+1):
            ans = max(ans, a[i+1]-a[j])

    print(ans)

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    else:
        A = []
        Sum = []
        for i in range(n):
            A.append(int(input()))
        Wa = 0
        for i in range(0,n):
            Wa += A[i]
            Sum.append(Wa)
        for i in range(0 , n):
            for j in range(0 , i):
                Num = Sum[i] - Sum[j]
                Sum.append(Num)
        print(max(Sum))

Submission status: Accepted

Solution code:
n=int(input())
while(n!=0):
    list=[]
    list.append(int(input()))
    for i in range(1,n):
        num=int(input())
        list.append(max(num,num+list[i-1]))
    print(max(list))
    n=int(input())

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    while True:
        # ??????????????\???
        loop = int(input())
        if loop == 0:
            break
        data = [int(input()) for _ in range(loop)]

        # ???????????????
        max_total = max(data)  # ??£?¶?????????°???????????§????¨????
        total = 0
        for d in data:
            if d > 0:  # ??°??????+??§????????°?????±????°????
                total += d  # ????¨?????¶???????????¨?????????´??°????????????????¢????????????????
                if total > max_total:
                    max_total = total
            else:  # ??°??????-?????´?????????????????§????????£???????????????????????§??????????????????
                if total > abs(d):  # ???????????§??????????????????????????§????????°???total???????????????????¶??¶???????
                    total += d
                    # ???????????????????????????????????§???max_total?????´??°??????????????§?????????
                else:
                    total = 0  # ???????????????????????§??????????????????????????§??????????????§????¨??????????????????????????¬??????????????????????????????????

        # ???????????¨???
        print(max_total)

Submission status: Accepted

Solution code:
import sys

while True:
  n = sys.stdin.readline()
  if n == "0\n": break
  n = int(n)
  l = []
  for i in range(n):
    l.append(int(raw_input().rstrip()))
  max_sum=-100000000
  for i in range(-1, n):
    sm = 0
    for j in range(i+1, n):
      sm += l[j]
      if max_sum < sm:
        max_sum = sm
  print max_sum

Submission status: Accepted

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

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

    maxp = -100001
    maxcont = -100001
    for i in range(n):
        maxcont = max(a[i], maxcont + a[i])
        maxp = max(maxp, maxcont)

    print(maxp)

Submission status: Accepted

Solution code:
import sys
import math as mas

while True:
	n=int(input())
	if n==0:break
	a=[int(input()) for i in range(n)]
	ma=-100010
	for i in range(n):
		sum=0
		for j in range(i,n):
			sum+=a[j]
			ma=max(ma,sum)
	print(ma)

#for i in sys.stdin:
#	a,b=map(int,i.split())
#	print(gcd(a,b),lcm(a,b))

Submission status: Accepted

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

Submission status: Accepted

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

import sys
import os


def max_seq(A):
    s = []
    s.append(A[0])
    for i in range(1, len(A)):
        v = max(A[i], A[i] + s[i-1])
        s.append(v)
    return max(s)

while True:
    s = input().strip()
    if s == '0':
        break

    N = int(s)
    A = []
    for i in range(N):
        v = int(input())
        A.append(v)

    print(max_seq(A))

Submission status: Accepted

Solution code:


def solve(a_list):
    if len(list(filter(lambda x: x >= 0, a_list))) == 0:
        return max(a_list)

    dp = [0] * len(a_list)
    dp[0] = max(0, a_list[0])
    for i in range(1, len(dp)):
        dp[i] = max(0, a_list[i] + dp[i - 1])

    return max(dp)


def main():
    while True:
        n = int(input())
        if n == 0:
            break
        a_list = [int(input()) for _ in range(n)]
        print(solve(a_list))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


def solve(a_list):
    if len(list(filter(lambda x: x >= 0, a_list))) == 0:
        return max(a_list)

    dp = [0] * len(a_list)
    dp[0] = a_list[0]
    for i in range(1, len(dp)):
        dp[i] = max(a_list[i], a_list[i] + dp[i - 1])
    return max(dp)


def main():
    while True:
        n = int(input())
        if n == 0:
            break
        a_list = [int(input()) for _ in range(n)]
        print(solve(a_list))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


while True:
    num = int(input())

    if num == 0: 
        break
    
    list = []
    for i in range(num):
        list.append(int(input()))

    for i in range(1, num):
        list[i] = max(list[i - 1] + list[i], list[i])

    print(max(list))

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if not n:
        break
    l = [int(input()) for j in range(n)]
    s = [l[0]]
    for k, v in enumerate(l[1:]):
        s.append(max(v, v + s[k]))
    print(max(s))

Submission status: Accepted

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

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

    maximum=0
    for i in range(n+1):
        for j in range(i):
            maximum=max(maximum,a[i]-a[j])



    if maximum==0:
        b=[a[i+1]-a[i] for i in range(n)]
        maximum=max(b)

    print(maximum)

Submission status: Accepted

Solution code:
from sys import stdin

def getMax(array):
    mx = mx2 = array[0]
    for i in array[1:]:
        mx2 = max(i, mx2 + i)
        mx = max(mx, mx2)
    return mx

for line in stdin:
    n = int(line)
    if n == 0:
        break
    array = []
    for line in stdin:
        line = int(line)
        array.append(line)
        if len(array) == n:
            break
    print(getMax(array))

Submission status: Accepted

Solution code:

def partial_max(L):
    n=len(L)
    max=-100000000000
    max_i=0
    for i in range(n):
       if max < sum(L[:i+1]):
           max=sum(L[:i+1])
           max_i=i
    max = -100000000000
    max_j=0
    for j in range(n):
       if max < sum(L[j:]):
           max=sum(L[j:])
           max_j=j

    if max_i >= max_j:
        return sum(L[max_j:max_i+1])
    elif sum(L[max_j:])>sum(L[:max_i+1]):
        return sum(L[max_j:])
    else:
        return sum(L[:max_i+1])
n=int(input())
A=[]
while n!=0:
    A.append([int(input()) for i in range(n)])
    n=int(input())
for i in range(len(A)):
    print(partial_max(A[i]))

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    cum = [0]
    s = 0
    for i in range(n):
        s += int(input())
        cum.append(s)
    M = cum[1]
    for i in range(n):
        for j in range(i + 1, n + 1):
            if cum[j] - cum[i] > M:
                M = cum[j] - cum[i]
    print(M)

Submission status: Accepted

Solution code:
import sys

def solve(numbers):
    max = -sys.maxsize
    for i in range(0, len(numbers)):
        sum = 0
        for j in range(i, len(numbers)):
            sum += numbers[j]
            if sum > max:
                max = sum
    return max


while True:
    n = int(input())
    if n == 0:
        break
    numbers = []
    for i in range(0, n):
        numbers.append(int(input()))

    print(solve(numbers))

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    max_sum = max_ending_here = int(input())
    for i in range(1, n):
        a = int(input())
        max_ending_here = max(a, max_ending_here + a)
        max_sum = max(max_sum, max_ending_here)
    print(max_sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    minv = tmp = 0
    maxv = -500000
    for i in range(n):
        tmp += a[i]
        maxv = max(maxv, tmp - minv)
        minv = min(minv, tmp)
    print(maxv)

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline())
while n:
    l = list()
    for _ in range(n):
        l.append(int(input()))
    a = l.copy()
    for i in range(1,n):
        a[i] = max(a[i-1] + l[i], l[i])
    print(max(a))
    n = int(sys.stdin.readline())

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    sumlist=[]
    sum=0
    max=-100000
    if n==0:
        break
    for i in range(n):
         sumlist.append(int(input()))
    for i in range(n):
        sum=0
        for j in range(0,n-i):
            sum=sumlist[i+j]+sum
            if max<sum:
                max=sum

    print(max)