Created
October 28, 2015 15:20
-
-
Save ernestum/e6ddefcb086ff5f1a913 to your computer and use it in GitHub Desktop.
Linear Time Divide and Conquer Maximal Sum Subsequence Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- 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