## Algorithm


from random import randint, seed

import time

from support import *

seed()

global array_size
global array

# Fill the grid


@print_timing
def solve_array32(array):

    global array_size

    half_array = array_size / 2

    l_array = array[:half_array]
    r_array = array[half_array:]

    max_so_far = 0

    for x in xrange(half_array):
        sum = 0
        for y in l_array[x:]:
            sum += y
            max_so_far = max(max_so_far, sum)


    for x in xrange(half_array, array_size):
        sum = 0
        for y in r_array[x:]:
            sum += y
            max_so_far = max(max_so_far, sum)

    max_l_middle = 0
    max_r_middle = 0

    sum = 0
    for y in reversed(l_array):
        sum += y
        max_l_middle = max(max_l_middle, sum)


    sum = 0
    for y in r_array:
        sum += y
        max_r_middle = max(max_r_middle, sum)

    max_so_far = max(max_so_far, max_r_middle + max_l_middle)

    return max_so_far

@print_timing
def solve_array2(array):

    global array_size

    max_so_far = 0
    for x in xrange(array_size):
        sum = 0
        for y in array[x:]:
            sum += y
            max_so_far = max(max_so_far, sum)

        print x

    return max_so_far

@print_timing
def solve_array(array):

    global array_size

    max_so_far = 0
    for x in xrange(array_size):
        for y in xrange(x, array_size):
            sum = 0
            for z in xrange(x, y):
                sum += array[z]
            max_so_far = max(max_so_far, sum)

    return max_so_far

if __name__ == "__main__":
    max3 = solve_array32(array)
    max2 = solve_array3(array)

##support

from random import randint, seed

import time

seed()

array_size = 10000


array = []

def print_timing(func):
    def wrapper(*arg):
        t1 = time.clock()
        res = func(*arg)
        t2 = time.clock()
        print '%s took %0.3f ms' % (func.func_name, (t2-t1)*1000.0)
        return res
    return wrapper

for i in xrange(array_size):
    array.append(randint(-200,200))

@print_timing
def solve_array3(array):

    global array_size

    half_array = array_size / 2

    l_array = array[:half_array]
    r_array = array[half_array:]

    max_so_far = 0

    for x in xrange(half_array):
        sum = 0
        for y in l_array[x:]:
            sum += y
            max_so_far = max(max_so_far, sum)


    for x in xrange(half_array, array_size):
        sum = 0
        for y in r_array[x:]:
            sum += y
            max_so_far = max(max_so_far, sum)

    max_l_middle = 0
    max_r_middle = 0

    sum = 0
    for y in reversed(l_array):
        sum += y
        max_l_middle = max(max_l_middle, sum)


    sum = 0
    for y in r_array:
        sum += y
        max_r_middle = max(max_r_middle, sum)

    max_so_far = max(max_so_far, max_r_middle + max_l_middle)

    return max_so_far