#=======================================================================
# Author: Isai Damier
# Title: Maximum Sub-Array Sum
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
# Given an array of integers (possibly positive and negative),
# find the sub-array whose sum is maximum. The sub-array must have
# at least two elements.
# Note: a sub-array is a continuous segment of an array.
#
# Time-complexity: O(n)
#
# Sample Input: {-1, 2, -3, 12, 23, -4, -5}
# Sample Output: {12, 23}
#
# Dynamic Programming Strategy:
#
# Let's call the input array X. Then an easy solution to this problem
# proceeds as follows:
#
# 0] scan X from left to right, tracking the sum of the maximal
# sub-array that ends at index i.
# 1] scan X from right to left, tracking the sum of the maximal
# sub-array that ends at index j.
# 2] find the maximum starting and ending indices (i.e. iMax and jMax)
# 3] then answer is the sub-array bounded by the iMax and jMax.
#
# Implementing step 0 is actually easier than most people might at
# first suspect. If we define array m so that m[i] is the sum of the
# maximal sub-array that ends at index i, then for all i, m[i] is
# simply the greater of X[i] and m[i - 1] + X[i]. We will illustrate
# below.
#
# i sub-arrays ending at i sum of maximal sub-array
# 0 {-1} m[0]=-1 : {-1}
# 1 {-1,2}; {2} m[1]=2 : {2}
# 2 {-1,2,-3}; {2,-3};{-3} m[2]=-1 : {2,-3}
# 3 {-1,2,-3,12};{2,-3,12};{-3,12};{12} m[3]=12 : {12}
#
# At every step we pick the maximal sub-array from the bunch. If the
# best sub-array ending at X[i-1] has a negative sum, i.e. m[i-1] < 0,
# then there is no benefit to concatenating X[i-1] to X[i] since it
# will pull X[i] down. On the other hand if m[i-1] is positive, the
# best sub-array ending at i will be the one we picked at i-1 added
# to X[i], as in the case where we picked {2,-3} over {-3} at i=2.
#
# The final tally are
#
# for step 0 is m={-1, 2, -1, 12, 35, 31, 26}
# and for step 1 is m={33, 34, 32, 35, 23, -4, -5}.
# Then for step 2, we use
# the results from step 0 to get m[iMax]=35 so that iMax=4;
# then we use the results from step 1 to get m[jMax]=35 so that jMax=3.
# Hence the final answers {A[jMax],...,A[iMax]} = {A[3],A[4]} = {12,23}
#=======================================================================
def subArraySum( A ):
m = [0] * len( A )
startingIndex = len( A ) - 1
endingIndex = 0
# find endingIndex
m[0] = A[0]
for i in range( 1, len( A ) ):
m[i] = max( A[i], m[i - 1] + A[i] )
if ( m[endingIndex] < m[i] ):
endingIndex = i
# find startingIndex
m = [0] * len( A )
m[len( A ) - 1] = A[len( A ) - 1]
for i in range( len( A ) - 2, -1, -1 ):
m[i] = max( A[i], m[i + 1] + A[i] )
if m[startingIndex] < m[i]:
startingIndex = i
if endingIndex <= startingIndex:
return None # no array size less than 2 allowed
result = A[startingIndex:endingIndex + 1]
return result
import unittest
from dynamic_programming import MaxSubarray as algorithm
class Test( unittest.TestCase ):
def testSubArraySum( self ):
lastTwo = [-1, -2, -3, -4, -5, 6, 7]
expResult = [6, 7]
result = algorithm.subArraySum( lastTwo )
self.assertEquals( expResult, result )
firstTwo = [8, 9, -1, -2, -3, -4, -5]
expResult = [8, 9]
result = algorithm.subArraySum( firstTwo )
self.assertEquals( expResult, result )
midTwo = [-1, -2, -3, 12, 23, -4, -5]
expResult = [12, 23]
result = algorithm.subArraySum( midTwo )
self.assertEquals( expResult, result )
midWithNegative = [-1, -2, -3, 12, -4, 23, 0, -4, -5]
expResult = [12, -4, 23]
result = algorithm.subArraySum( midWithNegative )
self.assertEquals( expResult, result )
flat = [0, 0, 0, 0, 0, 0, 0, 0, 0]
expResult = None
result = algorithm.subArraySum( flat )
self.assertEquals( expResult, result )
negatives = [-1, -2, -3, -4, -5]
expResult = None
result = algorithm.subArraySum( negatives )
self.assertEquals( expResult, result )
positives = [1, 2, 3, 4, 5, 6, 7]
result = algorithm.subArraySum( positives )
self.assertEquals( positives, result )
flatBump = [0, 0, 0, 0, 0, 0, 1]
expResult = None
result = algorithm.subArraySum( flatBump )
self.assertEquals( expResult, result )
flatMidBump = [0, 0, 0, 0, 1, 0, 0]
expResult = None
result = algorithm.subArraySum( flatMidBump )
self.assertEquals( expResult, result )
negativeBump = [-1, -1, -1, -1, -1, -1, 1]
expResult = None
result = algorithm.subArraySum( negativeBump )
self.assertEquals( expResult, result )
negativeMidBump = [-1, -1, -1, -1, 1, -1, -1, -1]
expResult = None
result = algorithm.subArraySum( negativeMidBump )
self.assertEquals( expResult, result )
