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: Wrong Answer

Solution code:
while True:
    cnt = -10000
    n = int(raw_input())
    if n == 0:
        break
    else:
        tmp = 0
        for i in range(n):
            tmp += int(raw_input())
            cnt = max(cnt,tmp)
    print cnt

Submission status: Wrong Answer

Solution code:
while True:
    cnt = -100000
    n = int(raw_input())
    if n == 0:
        break
    else:
        tmp = 0
        for i in range(n):
            tmp += int(raw_input())
            cnt = max(cnt,tmp)
    print cnt

Submission status: Wrong Answer

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 i>0 and nkeep>=0:
            nkeep+=i
        elif nkeep<0:
            nkeep=i
        if nans<nkeep:nans=nkeep
    if max(nlist)<0:nans=max(nlist)
    print(nans)

Submission status: Wrong Answer

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

    print(num)

Submission status: Wrong Answer

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

n = []
a = []

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

count = 0
for i in range(0,len(n)):
    sumMax = 0
    for j in range(count,count + n[i]):
        tmp = a[j]
        for k in range(j,count + n[i]):
            if j==k:
                continue
            tmp += a[k]
            sumMax = max(sumMax,tmp)
    count += n[i]
    print(sumMax)

Submission status: Wrong Answer

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(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: Wrong Answer

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

n = []
a = []

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

count = 0
for i in range(0,len(n)):
    sumMax = 0
    for j in range(count,count + n[i]):
        tmp = 0
        for k in range(j,count + n[i]):
            tmp += a[k]
            sumMax = max(sumMax,tmp)
    count += n[i]
    print(sumMax)

Submission status: Wrong Answer

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

n = []
a = []

i = 0
while True:
    n.append(int(input()))
    if n[i] == 0:
        n.pop()
        break
    for j in range(0,n[i]):
        a.append(int(input()))
    i += 1

count = 0
for i in range(0,len(n)):
    sumMax = 0
    for j in range(count,count + n[i]):
        tmp = 0
        for k in range(j,count + n[i]):
            tmp += a[k]
            sumMax = max(sumMax,tmp)
    count += n[i]
    print(sumMax)

Submission status: Wrong Answer

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 = [[-1000000 for j in range(n+1)] for i 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: Wrong Answer

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

i = 0
while True:
    n = int(input())
    if n == 0:
        break
    a = []
    for i in range(0,n):
        a.append(int(input()))
    sumMax = 0
    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: Wrong Answer

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 = -10001
    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: Wrong Answer

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 = -10001
    for i in range(0,n):
        tmp = 0
        for j in range(i,n):
            tmp += a[j]
            if tmp > sumMax:
                sumMax = tmp
    print(sumMax)

Submission status: Wrong Answer

Solution code:
while True:
    n=int(input())
    if n == 0:
        break
    s=0
    for _ in range(n):
        i = int(input())
        if i > 0: s+=i

    print(s)

Submission status: Wrong Answer

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

    ans=0
    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: Wrong Answer

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

    ans=0
    l=[]

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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(r,m)
	print r

Submission status: Wrong Answer

Solution code:
while True:
    n = int(raw_input())
    if n == 0: break
    
    data_set = [int(raw_input()) for i in xrange(n)]
    
    start_index = -1
    minus_index = -1
    stop_index = -1
    answer = 0
    for index, num in enumerate(data_set):
        if num > 0:
            if start_index == -1:
                start_index = index
            elif minus_index != -1:
                stop_index = index
        elif num <=  0:
            if start_index != -1 and minus_index == -1:
                minus_index = index 
        
        if stop_index != -1:
            total = sum(data_set[start_index:minus_index])
            if not answer or total > answer:
                answer = total
            minus_index = -1
            stop_index = -1
    else:
        if not answer:
            answer = sum(data_set[start_index:minus_index])
        total = sum(data_set[start_index:])
        if total > answer:
            answer = total
        
        print answer

Submission status: Wrong Answer

Solution code:
while True:
    n = int(raw_input())
    if n == 0: break
    
    data_set = [int(raw_input()) for i in xrange(n)]
    
    start_index = -1
    minus_index = -1
    stop_index = -1
    answer = 0
    max_minus = ''
    for index, num in enumerate(data_set):
        if num > 0:
            if start_index == -1:
                start_index = index
            elif minus_index != -1:
                stop_index = index
        elif num <=  0:
            if max_minus == '' or num > max_minus:
                max_minus = num
            if start_index != -1 and minus_index == -1:
                minus_index = index 
        
        if stop_index != -1:
            total = sum(data_set[start_index:minus_index])
            if not answer or total > answer:
                answer = total
            minus_index = -1
            stop_index = -1
    else:
        if not answer:
            answer = sum(data_set[start_index:minus_index])
        total = sum(data_set[start_index:])
        if total > answer:
            answer = total
        if start_index == -1:
            print max_minus
        else:
            print answer

Submission status: Wrong Answer

Solution code:
import sys

n = 1

while 1:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    print(sum(a))

Submission status: Wrong Answer

Solution code:
import sys

while 1:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    sumMax = 0
    s = []

    for i in range(len(a)+1):
        s.append(sum(a[0:i]))

    for i in range(len(a)+1):
        for j in range(1, len(a)+1):
            if (s[j] - s[i-1]) > sumMax:
                sumMax = s[j] - s[i-1]

    print(sumMax)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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, 0)
		res = max(s, res)
	
	print(res)

Submission status: Wrong Answer

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, 0)
		res = max(s, res)
	
	print(res)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 = a[1]
        for j in range(n + 1):
            for k in range(n + 1):
                ans = max(ans, a[k] - a[j])
        print(ans)

Submission status: Wrong Answer

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 = -1000000
        for j in range(n + 1):
            for k in range(n + 1):
                ans = max(ans, a[k] - a[j])
        print(ans)

Submission status: Wrong Answer

Solution code:
while(1):
    n = int(input())
    if n == 0:
        break
    else:
        ary = []
        mx = 0
        for i in range(n):
            ary.append(int(input()))
        for i in range(1, n + 1):
            sm = sum(ary[0:i])
            if mx < sm:
                mx = sm
            for j in range(1, n - i + 1):
                sm = sm - ary[j - 1] + ary[j + i - 1]
                if mx < sm:
                    mx = sm
        print(mx)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 = []
        minus_only=True
        for i in xrange(n):
            innum=input()
            nums.append(innum)
            if minus_only and innum>0:
                minus_only = False
        if minus_only:
            print max(nums)
        else:
            while len(nums)>1:
                nums = maxSumSequence(nums)
            print nums[0]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

def maxSumSequence(nums,plusmax=0):
    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 plusmax<max(pluslist):
        plusmax=max(pluslist)
    #??????????????????????????????????????????
    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,plusmax

def main():
    while True:
        n=input()
        if n==0:
            break
        nums = []
        minus_only=True
        for i in xrange(n):
            innum=input()
            nums.append(innum)
            if minus_only and innum>0:
                minus_only = False
        if minus_only:
            print max(nums)
        else:
            plusmax=0
            while len(nums)>1:
                nums,plusmax = maxSumSequence(nums,plusmax)
            if nums[0]<plusmax:
                print plusmax
            else:
                print nums[0]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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(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: Wrong Answer

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

    smax = A[0]
    ssum = A[0]
    for a in A[1:]:
        if a + ssum > smax:
            smax = a + ssum
        ssum = max(ssum+a, 0)    
        
    print(smax)

Submission status: Wrong Answer

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

    t = [int(input()) for i in range(n)]
    m = sum(t)
    while len(t) > 1:
        if t[0] < t[-1]:
            a = t.pop(0)
        else:
            a = t.pop(-1)
        if a < 0:
            m = max(sum(t), m)

    print(m)

Submission status: Wrong Answer

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,n+1):
            if max_a<wa[j]-wa[i]:
                max_a=wa[j]-wa[i]
    print(max_a)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    max_ = -999999
    a = [int(input()) for x in range(n)]
    for i in range(n - 1):
        m = a[i]
        for j in range(i + 1, n):
            m += a[j]
            if m > max_:
                max_ = m
    print(max_)

Submission status: Wrong Answer

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    max_ = -999999
    a = [int(input()) for x in range(n)]
    for i in range(n):
        m = a[i]
        for j in range(i + 1, n):
            m += a[j]
            if m > max_:
                max_ = m
    print(max_)

Submission status: Wrong Answer

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    max_ = -10000000
    a = [int(input()) for x in range(n)]
    for i in range(n - 1):
        m = a[i]
        for j in range(i + 1, n):
            m += a[j]
            if m > max_:
                max_ = m
    print(max_)

Submission status: Wrong Answer

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    max_ = -1000000
    a = [int(input()) for x in range(n)]
    for i in range(n - 1):
        m = a[i]
        for j in range(i + 1, n):
            m += a[j]
            if m > max_:
                max_ = m
    print(max_)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
while 1:
    r = 0
    n = input()
    if n == 0: break
    nums = []
    for i in xrange(n):
        nums.append(input())
    for i in xrange(n):
        if nums[i] < 0: continue
        sums = [0]
        for j in nums[i:]:
            sums.append(sums[-1] + j)
        r = max(sums) if r < max(sums) else r
    print r

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
while True:
    n = int(input())
    if n==0: break
    line = [int(input()) for i in range(n)]
    sum_li = [sum(line[:i]) for i in range(1,n+1)]
    key = sum_li.index(max(sum_li))+1
    result = [sum(line[i:key]) for i in range(key)]
    print(max(result))

Submission status: Wrong Answer

Solution code:
n=int(input())
while(n!=0):
    index=0
    list=[]
    sum=0
    max=0
    for i in range(n):
        list.append(int(input()))

    while (index < len(list) and list[index] < 0):
        index += 1

    while (index < len(list) and list[index] >= 0):
        sum += list[index]
        index += 1

    max=sum

    while(index<len(list)):
        plus_sum = 0
        minus_sum = 0

        while (index < len(list) and list[index] < 0):
            minus_sum += list[index]
            index += 1

        while (index < len(list) and list[index] >= 0):
            plus_sum += list[index]
            index += 1

        if abs(minus_sum)<plus_sum:
            sum+=(minus_sum+plus_sum)
            if max<sum: max=sum
        else:
            sum=plus_sum
            if max<sum: max=sum
    print(max)
    n=int(input())

Submission status: Wrong Answer

Solution code:
n=int(input())
while(n!=0):
    index=0
    list=[]
    sum=0
    max=0
    for i in range(n):
        list.append(int(input()))

    while (index < len(list) and list[index] < 0):
        sum += list[index]
        index += 1

    max=sum
    sum=0

    while (index < len(list) and list[index] >= 0):
        sum += list[index]
        index += 1

    if sum>0: max=sum

    while(index<len(list)):
        plus_sum = 0
        minus_sum = 0

        while (index < len(list) and list[index] < 0):
            minus_sum += list[index]
            index += 1

        while (index < len(list) and list[index] >= 0):
            plus_sum += list[index]
            index += 1

        if abs(minus_sum)<plus_sum:
            sum+=(minus_sum+plus_sum)
            if max<sum: max=sum
        else:
            sum=plus_sum
            if max<sum: max=sum
    print(max)
    n=int(input())

Submission status: Wrong Answer

Solution code:
n=int(input())
while(n!=0):
    index=0
    list=[]
    sum=0
    max=0
    for i in range(n):
        list.append(int(input()))
    max=list[0]
    while (index < len(list) and list[index] < 0):
        if max<list[index]: max = list[index]
        index += 1

    while (index < len(list) and list[index] >= 0):
        sum += list[index]
        index += 1

    if sum>0: max=sum

    while(index<len(list)):
        plus_sum = 0
        minus_sum = 0

        while (index < len(list) and list[index] < 0):
            minus_sum += list[index]
            index += 1

        while (index < len(list) and list[index] >= 0):
            plus_sum += list[index]
            index += 1

        if abs(minus_sum)<plus_sum:
            sum+=(minus_sum+plus_sum)
            if max<sum: max=sum
        else:
            sum=plus_sum
            if max<sum: max=sum
    print(max)
    n=int(input())

Submission status: Wrong Answer

Solution code:
n=int(input())
while(n!=0):
    index=0
    list=[]
    sum=-1
    max=0
    for i in range(n):
        list.append(int(input()))
    max=list[0]
    while (index < len(list) and list[index] < 0):
        if max<list[index]: max = list[index]
        index += 1

    while (index < len(list) and list[index] >= 0):
        sum += list[index]
        index += 1

    if sum>=0: max=sum

    while(index<len(list)):
        plus_sum = 0
        minus_sum = 0

        while (index < len(list) and list[index] < 0):
            minus_sum += list[index]
            index += 1

        while (index < len(list) and list[index] >= 0):
            plus_sum += list[index]
            index += 1

        if abs(minus_sum)<plus_sum:
            sum+=(minus_sum+plus_sum)
            if max<sum: max=sum
        else:
            sum=plus_sum
            if max<sum: max=sum
    print(max)
    n=int(input())

Submission status: Wrong Answer

Solution code:
n=int(input())
while(n!=0):
    index=0
    list=[]
    sum=0
    max=0
    for i in range(n):
        list.append(int(input()))
    max=list[0]
    while (index < len(list) and list[index] < 0):
        if max<list[index]: max = list[index]
        index += 1


    while (index < len(list) and list[index] >= 0):
        sum += list[index]
        index += 1

    if sum>=0: max=sum

    while(index<len(list)):
        plus_sum = 0
        minus_sum = 0

        while (index < len(list) and list[index] < 0):
            minus_sum += list[index]
            index += 1

        while (index < len(list) and list[index] >= 0):
            plus_sum += list[index]
            index += 1

        if abs(minus_sum)<plus_sum:
            sum+=(minus_sum+plus_sum)
            if max<sum: max=sum
        else:
            sum=plus_sum
            if max<sum: max=sum
    print(max)
    n=int(input())

Submission status: Wrong Answer

Solution code:
n=int(input())
while(n!=0):
    index=0
    list=[]
    sum=0
    max=0
    break_flag=False
    for i in range(n):
        list.append(int(input()))
    max=list[0]
    while (index < len(list) and list[index] < 0):
        if max<list[index]: max = list[index]
        index += 1

    if index==len(list):
        print(max)
        break_flag=True

    if not break_flag:
        while (index < len(list) and list[index] >= 0):
            sum += list[index]
            index += 1

        if sum>=0: max=sum

        while(index<len(list)):
            plus_sum = 0
            minus_sum = 0

            while (index < len(list) and list[index] < 0):
                minus_sum += list[index]
                index += 1

            while (index < len(list) and list[index] >= 0):
                plus_sum += list[index]
                index += 1

            if abs(minus_sum)<plus_sum:
                sum+=(minus_sum+plus_sum)
                if max<sum: max=sum
            else:
                sum=plus_sum
                if max<sum: max=sum
        print(max)
    n=int(input())

Submission status: Wrong Answer

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

        # ???????????????
        max_total = 0  # ??£?¶?????????°???????????§????¨????
        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: Wrong Answer

Solution code:
n = int(input())
while n > 0:
    q = 0
    m = 0
    for j in range(n):
        i = int(input())
        if q == 0:
            if i <= 0:
                continue
            else:
                q = i
        else:
            q += i
            if q < 0:
                q = 0
            else:
                m = max(m,q)
    print(m)
    n = int(input())

Submission status: Wrong Answer

Solution code:
n = int(input())
while n > 0:
    q = 0
    m = 0
    a = -100000
    for j in range(n):
        i = int(input())
        if i <= 0:
            a = max(a,i)
        if q == 0:
            if i <= 0:
                continue
            else:
                q = i
        else:
            q += i
            if q <= 0:
                q = 0
            else:
                m = max(m,q)
    print(m if m > 0 else a)
    n = int(input())

Submission status: Wrong Answer

Solution code:
n = int(input())
while n > 0:
    s = []
    m = 0
    for i in range(n):
        m += int(input())
        s.append(m)
    print(max(s))
    n = int(input())

Submission status: Wrong Answer

Solution code:
n = int(input())
while n > 0:
    s = [0]
    m = 0
    for i in range(n):
        m += int(input())
        s.append(m)
    m = s[0]
    for i in range(1,n+1):
        for j in s[0:i]:
            m = max(m,s[i]-j)
    print(m)
    n = int(input())

Submission status: Wrong Answer

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