Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Linear Time Divide and Conquer Maximal Sum Subsequence Algorithm
# -*- coding: utf-8 -*-
import random
'''
ACTUAL ALGORITHM START
'''
def getMaximumSumSubsequenceInformation(sequence, start, end):
'''
Returns information regarding the subsequence with maximal sum in the given
sequence between start and end. Will also return the total sum and
information about the maximal sum subsequence staring at 'start' and the
maximal sum subsequence ending at 'end'. Specifically it will return in that order:
totalSum - The sum over all values from start to end (end exclusive)
maxSubseqStart - The start index of the maximal sum subsequene between start and end
maxSubseqEnd - The (exclusive) end index of the maximal sum subsequence between start and end
maxSubseqSum - The sum of the maximal subsequene sum between start and end
maxLeftSubseqEnd - The (exclusive) end of the maximal sum subsequence starting at start
maxLeftSubseqSum - The sum of the maximal sum subsequence starting at start
maxRightSubseqStart - The start of the maximal sum subsequence ending at end
maxRightSubseqSum - The sum of maximal sum subsequence ending at end
'''
totalSum = None
maxSubseqStart = None
maxSubseqEnd = None
maxSubseqSum = None
maxLeftSubseqEnd = None
maxLeftSubseqSum = None
maxRightSubseqStart = None
maxRightSubeqSum = None
if end - start is 1:
totalSum = sequence[start]
maxSubseqStart = start
maxSubseqEnd = end
maxSubseqSum = sequence[start]
maxLeftSubseqEnd = end
maxLeftSubseqSum = sequence[start]
maxRightSubseqStart = start
maxRightSubeqSum = sequence[start]
else:
center = (start + end)/2
#Compute the subsequence information for the right an left side
left_totalSum, \
left_maxSubseqStart, \
left_maxSubseqEnd,\
left_maxSubseqSum, \
left_maxLeftSubseqEnd, \
left_maxLeftSubseqSum, \
left_maxRightSubseqStart,\
left_maxRightSubeqSum = \
getMaximumSumSubsequenceInformation(sequence, start, center)
right_totalSum, \
right_maxSubseqStart, \
right_maxSubseqEnd, \
right_maxSubseqSum, \
right_maxLeftSubseqEnd, \
right_maxLeftSubseqSum, \
right_maxRightSubseqStart, \
right_maxRightSubeqSum = \
getMaximumSumSubsequenceInformation(sequence, center, end)
#Total Sum
totalSum = left_totalSum + right_totalSum
#Compute Maximal Sum Subsequence
#By default we use join
maxSubseqStart = left_maxRightSubseqStart
maxSubseqEnd = right_maxLeftSubseqEnd
maxSubseqSum = left_maxRightSubeqSum + right_maxLeftSubseqSum
#Check if the maximum from the left side would be better
#and adopt it if so
if left_maxSubseqSum > maxSubseqSum:
maxSubseqSum = left_maxSubseqSum
maxSubseqStart = left_maxSubseqStart
maxSubseqEnd = left_maxSubseqEnd
#Check if the maximum from the right side would be better
#and adopt it if so
if right_maxSubseqSum > maxSubseqSum:
maxSubseqSum = right_maxSubseqSum
maxSubseqStart = right_maxSubseqStart
maxSubseqEnd = right_maxSubseqEnd
#Compute the maximal subsequence starting at the left border
#By default we merge the left border from the right side
#and the left border from the left side
maxLeftSubseqEnd = right_maxLeftSubseqEnd
maxLeftSubseqSum = left_totalSum + right_maxLeftSubseqSum
#Here we check if just the one from the left would be better
if left_maxLeftSubseqSum > maxLeftSubseqSum:
maxLeftSubseqSum = left_maxLeftSubseqSum
maxLeftSubseqEnd = left_maxLeftSubseqEnd
#Compute the maximal subsequence ending at the right border
#By default we merge the right border from the left side
#and the right border from the right side
maxRightSubseqStart = left_maxRightSubseqStart
maxRightSubeqSum = right_totalSum + left_maxRightSubeqSum
#Here we check if just the one from the right would be better
if right_maxRightSubeqSum > maxRightSubeqSum:
maxRightSubeqSum = right_maxRightSubeqSum
maxRightSubseqStart = right_maxRightSubseqStart
return totalSum, \
maxSubseqStart, \
maxSubseqEnd, \
maxSubseqSum, \
maxLeftSubseqEnd, \
maxLeftSubseqSum, \
maxRightSubseqStart, \
maxRightSubeqSum
def getMaximumSumSubsequence(sequence):
totalSum, maxSubseqStart, maxSubseqEnd, maxSubseqSum, maxLeftSubseqEnd, maxLeftSubseqSum, maxRightSubseqStart, maxRightSubeqSum = getMaximumSumSubsequenceInformation(sequence, 0, len(sequence))
return maxSubseqStart, maxSubseqEnd, maxSubseqSum
'''
ACTUAL ALGORITHM END
'''
def getMaximumSumSubsequenceBF(sequence):
ranges = []
for i in range(len(sequence)):
for j in range(i+1, len(sequence)+1):
ranges.append([i, j, sum(sequence[i:j])])
return max(ranges, key = lambda(r) : r[2])
def isInRange(pos, theRange):
return pos >= theRange[0] and pos < theRange[1]
def randSequence(length):
return [random.randint(-10, 10) for i in range(length)]
#Check 10 times that we match the brute force solution
for i in range(10):
seq = randSequence(100)
#seq = [5, -10, 9, 5, 7]
maxSubseq = getMaximumSumSubsequence(seq)
maxSubseqBF = getMaximumSumSubsequenceBF(seq)
if maxSubseq[2] != maxSubseqBF[2]:
break
#Display the found subsequence along with the brute force found sequence (the BF solution has stars)
for id, s in zip(range(len(seq)), seq):
print ("*" if isInRange(id, maxSubseqBF) else " "), ("|" if isInRange(id, maxSubseq) else " "), id, "\t", s
#Print the maximum sum subequence sum
print "Opt", maxSubseqBF[2]
print "Mine", maxSubseq[2]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.