In [33]:
''' A collection of approaches to the maximum contiguous sequence sum problem.
Ends up recursive, but no multiple reuse, so not really dynamic programming.
'''
def maxContigSum1(x):
'''Basic idea first, storing intermediate results in an array.'''
n = len(x)
endingHere = [0]*n # endingHere[i] = best sum ending at i:my be length 0.
maxSoFar = endingHere[0] = max(0, x[0])
for i in range (1, n): # 1..n-1
endingHere[i] = max(endingHere[i-1] + x[i], 0)
maxSoFar = max(maxSoFar, endingHere[i])
return maxSoFar
def maxContigSum(x):
'''Don't need the second array since only use previous value!'''
n = len(x)
endingHere = 0
maxSoFar = 0
for i in range (0, n): # 1..n-1
endingHere = max(endingHere + x[i], 0)
maxSoFar = max(maxSoFar, endingHere)
return maxSoFar
def maxContigSumWithLocation(x):
'''Return (maxSum, startI, endI): value and location in sequence.'''
n = len(x)
endingHere = 0
maxSoFar = 0
bestStartI = 0 # start of optimal seq so far
bestEndI = -1 #end of optimal seq so far - initially empty
curStartI = 0 # start of best seq ending at current position
for i in range (0, n): # 1..n-1
endingHere = max(endingHere + x[i], 0)
if endingHere == 0:
curStartI = i+1
elif maxSoFar < endingHere:
bestStartI = curStartI
bestEndI = i
maxSoFar = endingHere
return (maxSoFar, bestStartI, bestEndI)
def maxContigSumNeg(x):
# Handles case with negative number.
# Taken from https://en.wikipedia.org/wiki/Maximum_subarray_problem
endingHere = x[0]
maxSoFar = x[0]
for i in x[1:]:
endingHere = max(endingHere + i, i)
maxSoFar = max(endingHere, maxSoFar)
return maxSoFar
def maxContigSumNegWithLoc(x):
# Handles case with negative number.
# Modified version of the functions above
endingHere = x[0]
maxSoFar = x[0]
bestStartI = 0
bestEndI = 0
curStartI = 0
for i in range(1,len(x)):
endingHere = max(endingHere + x[i], x[i])
if endingHere == x[i]:
curStartI = i
if maxSoFar < endingHere:
bestStartI = curStartI
bestEndI = i
maxSoFar = endingHere
return (maxSoFar, bestStartI, bestEndI)
#### Rest is for displaying results ############################
def showMaxSum(nums):
'''Display starting data and results.'''
(maxSum, startI, endI) = maxContigSumWithLocation(nums)
print "Max contiguous sum in ", nums,
print "is", maxSum, ": ", nums[startI : endI +1]
print "is", maxContigSum(nums)
print "is", maxContigSum1(nums)
print "is", maxContigSumNeg(nums)
(maxSum, startI, endI) = maxContigSumNegWithLoc(nums)
print "is", maxSum, ": ", nums[startI : endI +1]
showMaxSum([5, 15, -30, 10, -5, 40, 10, -20])
In [34]:
showMaxSum([-5, -15, -30, -10, -5, -40, -10, -20])
In [35]:
showMaxSum([-50, -15, -30, -10, -5, -40, -10, -20])
In [ ]:
In [ ]: