Answer :
See John Bentley (1986) Programming Perls Addison Wesley for discussion of various implementations, ranging from brute force, O(n^3), solution which remembers previous sums O(n^2), divide and conquer O(n log(n)) and the linear approach. The book can be downloaded here
See also : V.V. Muniswamy in Design And Analysis Of Algorithms
The below code in python uses the technique described in Muniswamy and Bentley above, using dynamic programming and runs in linear time:
a = [31, -41, 59, 26, -53, 58, 97, -93, -23, 84]
def linear_method2():
maxsofar = 0
maxhere = 0
for i in range(0, len(a)):
maxhere = max(maxhere + a[i], 0)
maxsofar = max(maxsofar, maxhere)
print( a[:i+1])
print( 'maxhere %d maxsofar %d ' % (maxhere, maxsofar) )
print( maxsofar)
def linear_method1():
# [a] [b] [c] [d] [e] [f] [g] ...
# | | | |
# L U i-1 i
L = 0 # lowerbound of the max subarray
U = 0 # upperbound of the max subarray
summax = 0 # the current max subarray sum, i.e sum(a[L:U])
sumcur = 0 # the current sum from L to i-1
for i in range(0, len(a) ):
# If introducing the next element increases the maximum sum,
# then include the element
if (a[i]+sumcur) > summax and sumcur>0 :
print( ' (a[i]+sumcur) > summax ')
U = i
sumcur += a[i]
summax = sumcur
# If the current element cannot be introduced above ( since there are -ve in b/w ),
# but current element is greater than max sum so far => start from this point
elif a[i] > summax:
print( 'a[i] > summax' )
L=i
U=i
summax = sumcur = a[i]
# increase the current sum
else:
sumcur += a[i]
print( 'sumcur %d summax %d L %d U %d Array %s' % (sumcur, summax, L, U, a[L:U+1]) )
print('maxsubarray : %s' % a[L:U+1])
print('sum : %d' % summax)
linear_method2()
print('------------')
linear_method1()
See also : http://en.wikipedia.org/wiki/Maximum_subarray_problem
