Producing and comparing maximum sub array sum algorithms

Question

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 function_timer(function, array, policy):
    start_time = timeit.default_timer()
    if policy == "divide and conquer":
        print("Maximum sub sum for the %s algorithm: %s" 
            % (policy, function(array, 0, len(array) - 1)))
    else:
        print("Maximum sub sum for the %s algorithm: %s" % (policy, function(array)))
    print("Running Time: %s seconds.\n" % (timeit.default_timer() - start_time))



magnitude = input('enter vector size: ')
number_list = generate_array(magnitude, -10, 10)

function_timer(max_subarray_cubic, number_list, "cubic")
function_timer(max_subarray_quadratic, number_list, "quadratic")
function_timer(max_subarray_div_conquer, number_list, "divide and conquer")
function_timer(max_subarray_kadane, number_list, "kadane")

I would like:

1. To know if this is Pythonic? Am I accurately following conventions?
2. A general review on the accuracy of the algorithms. To the best of my knowledge I completed the requirements, but just in case. Focusing on the divide and conquer algorithm as it heavily differs and the cubic solution, it's surprisingly difficult to think about how to solve something poorly.
3. Feedback on the way I measure running time. I gave myself a means to run tests but how effective is it? How reliable are the results?

Answer 1

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 <module>
      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 this file is executed – whether directly as a script, or imported as a module. A better construction is to put this code inside if __name__ == '__main__', which means it will only be called if the script is run directly.

  That allows you to import functions from this file without any of this timing code being called.

Answer 2

I'll add a couple small notes on general Pythonic style, since alexwlchan convered the rest so well.

Python has lists, not arrays. Referring to things as arrays is mildly confusing and could be construed to mean that you're implementing some other class rather than the ordinary builtin.

You don't need to have an if else when you're returning a value as a result of the if statement, just remove the else and let the code continue if it hasn't returned yet.

def max_subarray_div_conquer(array, low, high):
    if low == high:
        return array[low]

    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))

You're using the old string formatting syntax, instead of % use the new format function. It has a lot of useful syntax so it's good to get used to.

print("Running Time: {} seconds.\n".format(timeit.default_timer() - start_time))

Answer 3

After fixing range bugs we have:

def max_subarray_cubic(array):
    maximum = float('-inf')
    for i in range(len(array)):
        for j in range(i, len(array)):
            current_sum = 0
            for k in range(i, j+1):
                current_sum += array[k]
            maximum = max(maximum, current_sum)
    return maximum

This could be improved by

• replacing the innermost loop with sum()
• eliminating the repetition of max function calls by turning the function into a generator and applying max over that

-

def subarray_sums(array):
    for i in range(len(array)):
        for j in range(i, len(array)):
            yield sum(array[i:j+1])

def max_subarray_cubic(array):
    return max(subarray_sums(array))