#!/usr/bin/python

def maxSubarray(array):
    cStart = 0
    cEnd = 0
    cSum = 0

    mStart = 0
    mEnd = 0
    mSum = array[0]

    i = 0

    while i < len(array):
        cEnd = i
        cSum += array[i]
        if cSum >= mSum:
            mSum = cSum
            mStart = cStart
            mEnd = cEnd
        if cSum < 0:
            cStart = i+1
            cEnd = i+1
            cSum = 0
        i = i + 1

    
    return array[mStart:mEnd+1]
            

def runTest( source, expected ):
    actual = maxSubarray(source)
    if actual != expected:
        print "FAILURE: Expected: ", expected, ", but got: ", actual
    else:
        print "Test Ok!"        

runTest([-1, 0, 5, 2, -3, 7], [0, 5, 2, -3, 7])
runTest([-2, -1, -2, -2, -3, -4], [-1])

runTest([1, 2, 3, 4, 5], [1, 2, 3, 4, 5])
runTest([5, -7, 5], [5])
runTest([5, -7, 6], [6])
runTest([6, -7, 5], [6])
runTest([0,0,0,0,0,0], [0,0,0,0,0,0])

print "The following test is supposed to fail: "
runTest([1,2,3], [3,2,1])