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:

import sys


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

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

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

Solution code:

import sys


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

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

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

Solution code:

import sys


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

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

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

Solution code:

import sys


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

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

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

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

    sumn = 0
    for i in range(n):
        sumn += int(raw_input())


    print sumn

Submission status: Wrong Answer

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)

    first = 0
    before = None

    for begin in xrange(num_data):
        sum = 0
        if begin > 0:
            first = data[begin - 1]

        if before is None:
            for i in xrange(begin, begin + length):
                if i >= num_data:
                    continue

                sum += data[i]

        else:
            if begin + length + 1 < num_data:
                sum = before - first + data[begin + length + 1]
            else:
                sum = before - first;

        before = sum

        if sum > max:
            max = sum

    return max


main()

Submission status: Wrong Answer

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

import sys


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):
    max = 0
    num_data = len(data)
    for l in xrange(1, num_data + 1):
        #print ("testing at l = " + str(l) + "..")
        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)

    sum = None
    old_head = 0

    #print "length = " + str(length)

    while True:
        if sum is None:
            sum = 0
            for i in xrange(0, length):
                sum += data[i]
            #print "initial = " + str(sum)
            max = sum

        else:
            if old_head + length < num_data:
                #print "sum = %d - %d + %d" % (sum, data[old_head], data[old_head + length])
                sum = sum - data[old_head] + data[old_head + length]
                #print "     = " + str(sum)
                if sum > max:
                    max = sum

                old_head += 1
            else:
                break

    return max

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python


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

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

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


def max_sum_sequence(data):
    max = 0
    num_data = len(data)
    for l in xrange(1, num_data + 1):
        # print ("testing at l = " + str(l) + "..")
        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)

    sum = None
    old_head = 0

    #print "length = " + str(length)

    while True:
        if sum is None:
            sum = 0
            for i in xrange(0, length):
                sum += data[i]
            #print "initial = " + str(sum)
            max = sum

        else:
            if old_head + length < num_data:
                #print "sum = %d - %d + %d" % (sum, data[old_head], data[old_head + length])
                sum = sum - data[old_head] + data[old_head + length]
                #print "     = " + str(sum)
                if sum > max:
                    max = sum

                old_head += 1
            else:
                break

    return max

main()

Submission status: Wrong Answer

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+1,len(a)):
            sum += a[j]
            if sum > max:
                max = sum
    print max

Submission status: Wrong Answer

Solution code:
n=input()
while n:
    x=0
    m=0
    s=0
    while n:
        a=input()
        x=max(x,0)+a
        m=max(m,x)
        n-=1
    print m
    n=input()

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
while n > 0:
  a = []
  for i in range(n):
    a.append(int(raw_input()))
  print max(a)
  n = int(raw_input())

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
ans = []
while n > 0:
  a = []
  for i in range(n):
    a.append(int(raw_input()))
  ans.append(sum(a))
  n = int(raw_input())
for i in ans:
  print i

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n=int(input())
    if n==0:break
    nlist=[]
    nans=[]
    for i in range(n):
        nlist.append(int(input()))
        for j in range(i+1):
            nn=0
            for k in range(j,i+1):
                nn+=nlist[k]
            nans.append(nn)
    print(max(nans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

import sys

lis = []
lis2 = []

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

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

Submission status: Time Limit Exceeded

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

import sys

lis = []
lis2 = []

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

while True:
  num = input()
  if num == 0:
    break
  else:
    lis = []
    lis2 = []
    maxnum = -99999
    for i in range(num):
      lis.append(input())
    for i in range(len(lis)):
      for j in range(i+1,len(lis)+1):
        su = sum(lis[i:j])
        if su > maxnum:
          maxnum = su
    print maxnum

Submission status: Time Limit Exceeded

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

for i in range(0,len(n)):
    sumMax = 0
    for j in range(sum(n[0:i-1 if i != 0 else 0]),sum(n[0:i])):
        for k in range(j,sum(n[0:i])+1):
            if j==k:
                continue
            sumMax = max(sumMax,sum(a[j:k]))
    print(sumMax)

Submission status: Time Limit Exceeded

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

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

    m = 0
    for i in range(0, len(a)):
        for j in range(i + 1, len(a) + 1):
            m = max(m, sum(a[i:j]))

    print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

    for i in range(len(a)+1):
        for j in range(i, len(a)+1):
            sums.append(sum(a[i:j]))

    print(max(sums))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

    print(sumMax)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

    print(sumMax)

Submission status: Time Limit Exceeded

Solution code:
def take(n, iterable):
    start, end = 0, n
    while True:
        chunk = iterable[start:end]
        if len(chunk) < n:
            raise StopIteration()
        yield chunk
        start += 1
        end += 1
while True:
    num = int(input())
    if not num: break
    data = [int(input()) for _ in range(num)]
    print(max((sum(chunk) for i in range(1,num+1) for chunk in take(i, data))))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n=input()
    if n==0:
        break
    else:
        a=[input() for _ in xrange(n)]
        ans=-float('inf')
        for i in xrange(n):
            for j in xrange(i,n):
                if ans<sum(a[i:j+1]):
                    ans=sum(a[i:j+1])
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n=input()
    if n==0:
        break
    else:
        a=[input() for _ in xrange(n)]
        ans=-float('inf')
        for i in xrange(n):
            for j in xrange(i,n):
                suma=sum(a[i:j+1])
                if ans<suma:
                    ans=suma
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    dataset = [int(input()) for _ in range(n)]
    r = []
    for i in range(n):
        for j in range(i, n + 1):
            r.append(sum(dataset[i:j]))
    print(sorted(r)[-1])

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    m = 0
    if n == 0:
        break
    dataset = [int(input()) for _ in range(n)]
    for i in range(n):
        for j in range(i, n + 1):
            s = sum(dataset[i:j])
        
            if m < s:
                m = s
    print(m)

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    m = -1000000 
    if n == 0:
        break
    dataset = [int(input()) for _ in range(n)]
    for i in range(n):
        for j in range(i, n + 1):
            if dataset[i:j] != []:
                s = sum(dataset[i:j])
                if m < s:
                    m = s
    print(m)

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    m = -1000000 
    if not n :
        break
    dataset = [int(input()) for _ in range(n)]
    for i in range(n):
        for j in range(i, n + 1):
            if dataset[i:j] != []:
                s = sum(dataset[i:j])
                if m < s:
                    m = s
    print(m)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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)):
            if i == len(a) - 1 or a[i] * a[i + 1] < 0:
                b.append(sum(a[:i + 1]))
                a[:i + 1] = []
                break
    print(max(max(sum(b[j:j + i + 1]) for j in range(len(b) - i)) for i in range(len(b))))

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    if n==0: break
    sum_li = [int(input()) for i in range(n)]
    for i in range(2,n+1):
        for j in range(n-i+1):
            sum_li.append(sum(sum_li[j:j+i]))
    print(sorted(sum_li)[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def solve(v):
    w = []
    for i in range(len(v)):
        for j in range(len(v[i:])):
            w.append(sum(v[i:(j+1)]))
    return(max(w))

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

        print(solve(v))

Submission status: Time Limit Exceeded

Solution code:
def solve0(v):
    w = []
    l = len(v)
    ans = max([sum(v[i:j+1]) for i in range(l) for j in range(i,l)])
    return(ans)

def sign(x):
    if x >= 0:
        s=+1
    else:
        s=-1
    return(s)

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

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

        print(solve(v))

Submission status: Time Limit Exceeded

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

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

    maxi = 0
    for i in range(1,1+n):
        for j in range(n-i+1):
            if maxi < sum(a[j:j+i]):
                maxi = sum(a[j:j+i])

    print(maxi)

Submission status: Time Limit Exceeded

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

import sys
import os

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

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

    max_value = 0
    for start_i in range(N):
        for end_i in range(start_i + 1, N):
            sum_value = sum(A[start_i:end_i+1])
            if sum_value > max_value:
                max_value = sum_value
    print(max_value)

Submission status: Time Limit Exceeded

Solution code:
def MSS(li):
    s = sum(li)
    l = len(li)
    for i in range(l):
        for j in range(l-i):
            if j == 0:
                continue
            e = l - j
            tmp = sum(li[i:e])
            if s < tmp:
                s = tmp
    return s


if __name__ == "__main__":
    assert MSS([-5, -1, 6, 4, 9, -6, -7]) == 19, "sample1"
    assert MSS([1, 2, 3, 2, -2, -1, 1, 2, 3, 2, 1, -2, 1]) == 14, "sample2"
    while True:
        n = int(input())
        if n == 0:
            break
        li = []
        for _ in range(n):
            li.append(int(input()))
        print(MSS(li))

Submission status: Time Limit Exceeded

Solution code:
def MSS(li):
    s = sum(li)
    l = len(li)
    for i in range(l):
        for j in range(l-i):
            if j == 0:
                continue
            e = l - j
            tmp = sum(li[i:e])
            if s < tmp:
                s = tmp
    return s


if __name__ == "__main__":
    assert MSS([-5, -1, 6, 4, 9, -6, -7]) == 19, "sample1"
    assert MSS([1, 2, 3, 2, -2, -1, 1, 2, 3, 2, 1, -2, 1]) == 14, "sample2"
    answer = []
    while True:
        n = int(input())
        if n == 0:
            break
        li = []
        for _ in range(n):
            li.append(int(input()))
        answer.append(MSS(li))
    print(*answer, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
while True:
    N=int(input())
    if N==0:
        break
    else:
        a=[]
        max=0
        for i in range(N):
            a.append(int(input()))
        for i in range(N):
            for j in range(N+1):
                    if sum(a[i:j])>=max:
                        max=sum(a[i:j])

        print(max)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(sys.stdin.readline())
while n:
    l = list()
    for _ in range(n):
        l.append(int(input()))

    maxs = 0
    for i in range(n):
        for j in range(i,n):
            s = 0
            for k in range(i,j+1):
                s += l[k]
            maxs = max(maxs,s)
    n = int(sys.stdin.readline())
    print(maxs)

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    sum_max = 0
    a = []
    for i in range(n):
        a.append(int(input()))
        for j in range(i + 1):
            sum_tmp = sum(a[j:i + 1])
            if sum_tmp > sum_max:
                sum_max = sum_tmp
    print(sum_max)

Submission status: Time Limit Exceeded

Solution code:
def wa(a,x,y):
    S = 0
    for i in range(x,y+1):
        S = S + a[i]
    return S

n = int(input())
while n != 0:
    a = []
    for i in range(n):
        a.append(int(input()))
    ans = a[0]
    for i in range(n):
        for j in range(i+1,n):
            ans = max(wa(a,i,j),ans)
    print(ans)
    n = int(input())

Submission status: Time Limit Exceeded

Solution code:
import math

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

def wa(a,x,y):
    S = 0
    for i in range(x,y+1):
        S = S + a[i]
    return S

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 sign(b[len(b)-1]) == sign(a[i]):
            b[len(b)-1] = b[len(b)-1] + a[i]
        else:
            b.append(a[i])

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
m=lambda x:max(map(max,[[sum(x[j:j+i+1]) for j in range(len(x)-i)] for i in range(len(x))]))
while True:
    n=int(input())
    if n==0:break
    print(m([int(input()) for i in range(n)]))

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n=int(input())
    if not n:break
    l=[int(input()) for _ in range(n)]
    print(max(sum(l[j:i]) for i in range(len(l)+1) for j in range(i)))

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n=int(input())
    if not n:break
    l=tuple([int(input()) for _ in range(n)])
    print(max(sum(l[j:i]) for i in range(len(l)+1) for j in range(i)))

Submission status: Time Limit Exceeded

Solution code:
while 1:
    m=0
    l=[]
    n=int(input())
    if not n: break
    for i in range(n):
        j=int(input())
        if i==0:
            m+=j
        elif s*j<0:
            l.extend([m])
            m=j
        else:
            m+=j
        s=j
    l.extend([m])
    b=len(l)
    print(max([sum(l[i:j]) for j in range(1,b+1) for i in range(j)]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n=input()
    if n == 0: break
    number = [0 for j in range(n)]
    sumpoyo = 0
    for i in range(n):
        number[i] = input()
    for i in range(1, n+1):
        for k in range(n-i+1):
            a = number[k:k+i]
            #print i,k
            #print a
            temp = sum(a)
            if temp > sumpoyo: sumpoyo = temp
    print sumpoyo

Submission status: Time Limit Exceeded

Solution code:
while True:
  a=int(input())
  if a==0:break
  g=[]
  for i in range(a):
    g.append(int(input()))
  ans=0
  for i in range(a):
    for j in range(a):
      hoge=sum(g[i:j+1])
      if hoge > ans:ans = hoge
  print ans

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    numbers = []
    for i in range(n):
        numbers.append(int(raw_input()))
    sigmas = []
    for i in range(1,n+1):
        for j in range(n+1-i):
            sigmas.append(reduce(lambda x,y:x+y,numbers[j:j+i+1]))
    print max(sigmas)

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    numbers = []
    for i in range(n):
        numbers.append(int(raw_input()))
    sigmas = []
    for i in range(1,n+1):
        for j in range(n+1-i):
            sigmas.append(reduce(lambda x,y:x+y,numbers[j:j+i+1]))
    print reduce(lambda x,y:x>y if x else y,sigmas)

Submission status: Time Limit Exceeded

Solution code:

while True:
    n = input();
    if n == 0:
        break;
    l = []
    for i in range(n):
        l.append(input());

    print max([max([sum(l[i:j + 1]) for j in range(i, len(l))]) for i in range(len(l))])

Submission status: Time Limit Exceeded

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

while True:
    n = int(stdin.readline())
    if not n:
        break
    m = 0
    tup = tuple(int(stdin.readline()) for _ in xrange(n))
    for i in xrange(len(tup)):
        for j in xrange(1 + i, len(tup) + 1):
            t = sum(tup[i:j])
            if t > m:
                m = t
    print(m)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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