2
\$\begingroup\$

I've implemented the algorithm below for the maximum contiguous subarray problem and would like a review on three specific things:

  1. Making the code shorter
  2. Making the code faster
  3. Any other algorithms that can do the job with lower complexity

def crossingsubarray(A, low, mid, high):

    negetiveinfinity = -10000000000
    summ = 0
    for i in range(mid, low - 1, -1):
        summ = summ + A[i]
        if summ > negetiveinfinity:
            negetiveinfinity = summ
            leftindex = i
    left = negetiveinfinity


    negetiveinfinity = -10000000000
    summ = 0

    for j in range(mid+1, high+1):
        summ = summ + A[j]
        if summ > negetiveinfinity:
            negetiveinfinity = summ
            rightindex = j
    right = negetiveinfinity

    return(leftindex, rightindex, left + right)



def findmaxarray(alist, low, high):

    if high == low:
        return low, high, alist[low]

    else:

        mid = (low+high)/2

        leftlow, lefthigh, leftsum = findmaxarray(alist, low, mid)
        rightlow, righthigh, rightsum = findmaxarray(alist, mid + 1, high)    
        crosslow, crosshigh, crosssum = crossingsubarray(alist, low, mid, high)         

        if leftsum >= rightsum and leftsum >= crosssum:
            return leftlow, lefthigh, leftsum
        elif rightsum >= leftsum and rightsum >= crosssum:
            return rightlow, righthigh, rightsum
        else:
            return crosslow, crosshigh, crosssum


B = [-7, -2, 5, 4, -1, 100, 10]

L,H,maxi = findmaxarray(B, 0, 6)

print(L)
print(H)
print(maxi)

Just a quick explanation:

The first function, crossingsubarray, returns the maximum value of a subarray (along with its low and high indices with respect to A) such that the subarray crosses the provided midpoint.

The second function, findmaxarray, is a divide-and-conquer task which recursively calls the first function such that the maximum contiguous subarray sum is found.

Please let me know if I could make any improvements in the aforementioned areas.

\$\endgroup\$
5
\$\begingroup\$

In this loop:

negetiveinfinity = -10000000000
summ = 0
for i in range(mid, low - 1, -1):
    summ = summ + A[i]
    if summ > negetiveinfinity:
        negetiveinfinity = summ
        leftindex = i
left = negetiveinfinity

First, 'negetiveinfinity' isn't a good variable name - it should be 'negative', for a start. More importantly, it doesn't reflect how you're using it - it "negative infinity" would be a number that always tests lower than any other number, but you're using it as the highest contiguous sum you've found so far. Similarly, you're using summ (another misspelling, although presumably this one is to avoid shadowing the builtin sum) as a trial total that you test to see if it is better than the stored one. Better names might be max_sum and trial_sum.

Then once you've found that, you reset those variables and reuse them in almost exactly the same loop on the other half of the list. Both of these loops also have a possible logic error: you start the trial sum at a 'sufficiently small' value. That can be problematic if it isn't small enough. Instead, it would be more usual to start it at the 'mid' value.

But the ideal thing to do here is to fix that error both times by factoring out the repeated code. You can do this really easily with a bit of analytic clarity of what your problem is: you're looking for the the maximum cumulative sum of the elements in a sequence. That immediately suggests using itertools.accumulate, like this:

left_half = it.accumulate(A[low-1:mid:-1])
right_half = it.accumulate(A[mid:high+1])
left = max(left_half, key=lambda x: x[1])
right = max(right_half, key=lambda x: x[1])
return (mid - left[0], mid + right[0], left[1] + right[1])

And that whole function is now five lines.

You can use do something similar here:

leftlow, lefthigh, leftsum = findmaxarray(alist, low, mid)
rightlow, righthigh, rightsum = findmaxarray(alist, mid + 1, high)    
crosslow, crosshigh, crosssum = crossingsubarray(alist, low, mid, high)

if leftsum >= rightsum and leftsum >= crosssum:
    return leftlow, lefthigh, leftsum
elif rightsum >= leftsum and rightsum >= crosssum:
    return rightlow, righthigh, rightsum
else:
    return crosslow, crosshigh, crosssum

You never use *low and *high separately, and you only use *sum to compare the three sets. So instead of using nine variables, use a single list of tuples and a single call to max:

candidates = [findmaxarray(alist, low, mid), 
              findmaxarray(alist, mid + 1, high), 
              crossingsubarray(alist, low, mid, high)]

return max(candidates, key=lambda x: x[2])

You appear to be using Python 2. In Python 3.x, this line:

mid = (low+high)/2

will actually cause an error further along your code. Division of two integers now returns a float, so that eg, 5/2 = 2.5 (instead of 2). Use floor division to guarantee an integer result:

mid = (low+high) // 2

If you can't upgrade to Python 3, I highly recommend at least putting yourself in as close-to-future proof environment as possible. Include this line:

from __future__ import division

at the top of your file to back port this particular behavior.


Slicing the array into left_half and right_half does start creating copies that you have otherwise avoided by passing low and high around. For the right half, you could not copy it by using it.islice. But that won't work for the left half, because islice doesn't support using a negative step. If this is a problem, you may want to consider using numpy - slicing numpy arrays doesn't create copies.


For mutual consistency, and to better describe what the 'crossing' one does, rename your two functions to max_crossing_subarray and max_subarray. The usual written rule seems to be that functions should be named with verb phrases, but in practice there are some exceptions to this - in my experience, for functions that would be named find_blah dropping the find_ seems to be preferred.


In terms of overall complexity, this previous question implements a C version of what appears to be the same algorithm as yours and claims to be O(n log n). The accepted answer points to Kadane's algorithm, a non-recursive O(n) solution. The Wikipedia page provides a Python implementation that only returns the actual sum, but claims that it can be modified to return the start and end indices as well.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.