Producing and comparing maximum sub array sum algorithms

This is an exercise in implementing the maximum sub-array sum problem.

It asks for several solutions of complexity:

• \$O(n)\$

• \$O(n \log n)\$

• \$O(n^2)\$

• \$O(n^3)\$

For an additional challenge I completed it using Python.

```
import random
import timeit

#random array generator
def generate_array(item_count, lower_bound, upper_bound):
number_list = []
for x in range(1, item_count):
number_list.append(random.randint(lower_bound, upper_bound))
return number_list

#cubic brute force O(n^3)
def max_subarray_cubic(array):
maximum = float('-inf')
for i in range(1, len(array)):
for j in range(i, len(array)):
current_sum = 0
for k in range(i, j):
current_sum += array[k]
maximum = max(maximum, current_sum)
return maximum

#quadratic brute force O(n^2)
def max_subarray_quadratic(array):
maximum = float('-inf')
for i in range(0, len(array)):
current = 0
for j in range(i, len(array)):
current += array[j]
maximum = max(current, maximum)
return maximum

#divide and conquer O(n*lg(n))
def max_cross_sum(array, low, mid, high):
left_sum = float('-inf')
sum_ = 0
for i in range(mid, low, -1):
sum_ += array[i]
left_sum = max(left_sum, sum_)

right_sum = float('-inf')
sum_ = 0
for i in range(mid + 1, high):
sum_ += array[i]
right_sum = max(right_sum, sum_)
return left_sum + right_sum

def max_subarray_div_conquer(array, low, high):
if low == high:
return array[low]
else:
mid = (low + high) / 2
return max(max_subarray_div_conquer(array, low, mid),
max_subarray_div_conquer(array, mid + 1, high),
max_cross_sum(array, low, mid, high))

#Kadane's algorithm O(n)
def max_subarray_kadane(array):
current = maximum = array[0]
for x in array[1:]:
current = max(x, current + x)
maximum = max(maximum, current)
return maximum

#to facilitate timing each algorithm
def

tl;dr: This is pretty good! A few bugs and weird edge cases, and you can be more Pythonic – no code is perfect – but I like what you’ve done.

Is this Pythonic?

There are several things you could do to make this more Pythonic:

-
Rather than describing functions using a comment above the definition, use a docstring – that’s the preferred way to document functions in Python.

-
Rather than iterating over the indexes of an array, it’s better to iterate over the elements. It’s the difference between (bad):

for index in range(len(myarray)):
    element = myarray[index]
    do_stuff_with_element()

and (good):

for element in myarray:
    do_stuff_with_element()

If you need both the index and the element, then you should use enumerate().

-
Indentation should be four spaces, not two.

-
Look at list comprehensions; they’re very useful. For example, they can reduce your generate_array() function to one line:

def generate_array(count, lower_bound, upper_bound):
    """
    Generates a random array of integers.
    """
    return [random.randint(lower_bound, upper_bound) for _ in range(count)]

Are these accurate implementations of the algorithms?

max_subarray_cubic()

-
Because all your ranges start at 1, but Python indexes lists at 0, this function doesn't seem to include the first element in the array. For example:

>>> max_subarray_cubic([1, 2, 3, -100])
5

but taking the first three elements gives a larger sum of 6. Adjusting the ranges to range(len(array)) seems to fix the problem.

max_subarray_quadratic()

-
I haven't spotted any bugs in it; this seems to work correctly.

-
As I explained above, you could make the inner loop more Pythonic by iterating over the elements, like so:

for elem in array[i:]:
    current += elem
    maximum = max(current, maximum)

max_cross_sum()

-
There should be something in the docstring to explain how to use the low/mid/high arguments; I had to guess and I think I got it wrong. [I didn't realise this was a helper function for max_subarray_div_conquer when I first read it.]

-
It's quite unusual to see a variable name with a trailing underscore in Python programs. Good job for not overriding the builtin function (a common mistake among new programmers), but you should try to pick a better variable name rather than just appending an underscore.

-
When the last argument of range() is -1, I prefer to use reversed(), because I think it's easier to read. Combining with my advice above, your first loop becomes:

for elem in reversed(array[low:mid]):
    sum += elem
    # do stuff with elem

max_subarray_div_conquer()

-
When this function is first called, I have to pass in the length of the array as arguments, which could cause a problem if I pass in incorrect values. I'm repeating information provided by the first argument.

It would be better to check if the user passes in any values, and if not, compute them based on the length of the array:

def max_subarray_div_conquer(array, low=None, high=None):
    if low is None:
        low = 0
    if high is None:
        high = len(array)

I'm using a default argument of None to check whether the user passed anything in; if they didn't, I'll work it out myself.

max_subarray_kadane()

-
If I pass this function an empty list, it hits an exception in the first line:

Traceback (most recent call last):
File "tmp/subarrays.py", line 89, in
function_timer(max_subarray_kadane, [], "kadane")
File "tmp/subarrays.py", line 76, in function_timer
print("Maximum sub sum for the %s algorithm: %s" % (policy, function(array)))
File "tmp/subarrays.py", line 63, in max_subarray_kadane
current = maximum = array[0]
IndexError: list index out of range


You should check that I've passed in more than just an empty list at the start of this function. You might still want to raise an exception – a ValueError seems appropriate here – but it should provide a more informative message about why something has gone wrong.

You might want to look at doing the same for the rest of your functions: although they don't throw an exception, they tell me that the maximum subarray sum of an empty list is -inf. Does that seem sensible? Is there a meaningful largest subarray sum of an empty list?

How's the running time function?

-
The function itself is fine. The fact that you have to special case the divide and conquer algorithm is a little annoying, but that can be addressed by removing the need for additional arguments – see above.

-
One weakness with the mechanism is that you only check the results once, and for a single array. It’s possible that you could get an array which plays to one algorithm's strengths, or a call is unlucky and takes unusually long time.

You'd get more accurate results if (a) you tested with a variety of arrays, and (b) you repeated and averaged the results.

-
Your test code is in the top-level of the file, which means it will be run whenever

StackExchange Code Review Q#105561, answer score: 11