maxsubarray.py

# Title: Max subarray
# Authors: Clay McLeod
# Description: Finds the max subarray of an array of integers, in O(nlogn) time
# Section: Python
# Subsection: Interesting Problems
#
# Problem description - http://en.wikipedia.org/wiki/Maximum_subarray_problem

import sys

def find_max_subarray(array):
    """---------------------------------------------------------------------
> Documentation

Author:      Clay McLeod
Course:      CSCI 533
Date:        Sept. 30, 2014
Assignment:  1

Method:      find_max_subarray(array)
Description: Finds the max subarray of an array of integers
Input:       A list of integers
Output:      1) The max subarray
             2) The cumulative sum of that max subarray (for output)
---------------------------------------------------------------------
    """

    # min subarray variables
    max_sum = -sys.maxint                                                # initialize max sum to -infinity
    max_sum_ending_index = -1                                            # keep track of the ending index of max sum                           

    # min cumsum variables
    min_cumsum = sys.maxint                                              # initialize min cumsum to -infinity
    min_cs_index = -1                                                    # keep track of min cumsum ending index

    # rolling cumsum variables
    current_cumsum = 0                                                   # running total of the sum, initialized to identity element
    current_index = 0                                                    # keep track of current index as we step through the loop
    
    for j in range(0, len(array)):                                       # from index 0 to index j-1 in the array
        current_index = current_index + 1                                # update the current iteration index
        current_cumsum = current_cumsum + array[j]                       # update cumsum to sum [1..j]
        if current_cumsum < min_cumsum:                                  # check if the minimum cumsum > current cumsum
            min_cumsum = current_cumsum                                  # update current minimum cumsum
            min_cs_index = current_index                                 # ""

        current_max_sum = current_cumsum - min_cumsum                    # max cumsum is either previous max cumsum or current cumsum - min cumsum
        if current_max_sum > max_sum:                                    # compare max cumsum to our current iteration's max sum
            max_sum = current_max_sum                                    # update current max subarray
            max_sum_ending_index = current_index                         # ""

    max_subarray = array[min_cs_index: max_sum_ending_index]             # max subarray is from i+1 to j (min_cs_index is i+1 because of how the loop is setup)
    return max_subarray, max_sum                                         # return maxsubarray with computed max sum value


# boilerplate

if __name__ == "__main__":

    # print documentation
    print find_max_subarray.__doc__

    # Input
    array = [1, -9, 2, -3, 8, 9, -1, 3, -1, 10]
    print "{0} {1}".format("Input:".ljust(8), array)
    
    # Calculation
    max_subarray, max_sum = find_max_subarray(array)

    # Output
    print "{0} The max subarray is {1}".format("Output:".ljust(8), max_subarray)
    print "{0} This subarray\'s cumulative sum is {1}".format("".ljust(8), max_sum)

output.txt

---------------------------------------------------------------------
> Documentation

Method:      find_max_subarray(array)
Description: Finds the max subarray of an array of integers
Input:       A list of integers
Output:      1) The max subarray
             2) The cumulative sum of that max subarray (for output)
---------------------------------------------------------------------
    
Input:   [1, -9, 2, -3, 8, 9, -1, 3, -1, 10]
Output:  Max subarray is [8, 9, -1, 3, -1, 10]
         This subarray's cumulative sum is 28