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

Solution (Python):
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)
        
        res=max(num, res)
        

    print(res)

Solution (Python):



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)

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

Solution (Python):



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)

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

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

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

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

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

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

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

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

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

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

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

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(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

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

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

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

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

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

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

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

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

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

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

Solution (Python):


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

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

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

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

Solution (Python):
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="")

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

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

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

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

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

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

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

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

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

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

    print(ans)

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

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

Solution (Python):
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 += d
                    
                else:
                    total = 0  

        
        print(max_total)

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

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

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

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

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

Solution (Python):


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))

Solution (Python):


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()

Solution (Python):


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()

Solution (Python):


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))

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

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

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

Solution (Python):

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]))

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):
while True:
    n = int(raw_input())
    if n != 0:
        max = -9999999999999
        a =[int(raw_input()) for i in range(n)]
        
        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

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

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

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

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

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

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

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

Solution (Python):



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)

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

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

Solution (Python):


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

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

Solution (Python):



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()

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

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

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

Solution (Python):

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)

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

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

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

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

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