Max Sum Sublist

five_stars.py

#!/usr/bin/python

"""
Tyler Brock for Five Stars - 2011

Write function f in python, that given a list of numbers
L returns i, j such that L[i:j] has maximal sum.

For example, if L = [1, -2, 3, 4, 5, -1] then f(L) should return (2, 5).
"""

def maxSumSublist(numbers):
    if not numbers: return None
    
    start_index, end_index = -1, 0
    current_start_index = -1
    max_so_far = 0
    current_sum = 0
    
    for index, number in enumerate(numbers):
        current_sum += number
        
        if current_sum >= max_so_far:
            max_so_far = current_sum
            start_index = current_start_index
            end_index = index
            
        elif current_sum <= 0:
            max_so_far = current_sum
            current_sum = 0
            current_start_index = index
        
    return (start_index + 1, end_index + 1)
    
if __name__ == "__main__":
    lists = []
    lists.append([])                        # empty list
    lists.append([0])                       # single item
    lists.append([-1])                      # single negative item
    lists.append([-10,-2])                  # consecutive negative item
    lists.append([1,-1,1])                  # returns seq of len 3
    lists.append([1,-2,1])                  # returns seq of len 1
    lists.append([-1,2])                    # returns (1, 2)
    lists.append([2,-1])                    # returns (0, 1)
    lists.append([-3, -2, -5, 1, 2, -1])    # returns (3, 5)
    lists.append([7, -6, 3, -15, 25, -1])   # returns (4, 4)
    lists.append([1, -2, 3, 4, 5, -1])      # returns (2, 5)
    
    for number_list in lists:
        print "Finding the Maximum Sum Sublist of the following list:"
        print number_list
        print "Max Sum Sublist =>", maxSumSublist(number_list)
        print