#!/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])