Linear Time Divide and Conquer Maximal Sum Subsequence Algorithm

MaximalSumSubsequence.py

# -*- 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]