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.
