Maximum subarray problem

Given a array with -ve and +ve integers, find the sub-array with maximum sum.

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