Python program to find the subarray with maximum sum

Question

An assignment at school required me to write a program for this task using Kadane's algorithm (explained here):

1. Define the function find_max_subarray that takes a list as an argument and two indices, start and end. It finds the maximum subarray in the range [start, end – 1].
2. The function find_max_subarray returns the tuple (l, r, m) where l and r are the left and right indices of the maximum subarray and m is its sum.
3. The function uses a loop to keep track of the maximum subarray ending at index i. That is, the maximum subarray that has the element at index i as its last element.
4. Then the maximum subarray will simply be the maximum of all these subarrays.
5. The maximum subarray ending at index i + 1 is given by max(list[i] + maximum sum of subarray ending at i, list[i]).
6. The function keeps track of the maximum sum of the subarray seen so far and its left and right indices as the loop iterates.

Here is my solution to this task (using Python):

def find_max_subarray(alist, start, end):

    max_ending_at_i = max_seen_so_far = alist[start]
    max_left_at_i = max_left_so_far = start
    max_right_so_far = start + 1
    for i in range(start + 1, end):
        if max_ending_at_i > 0:
            max_ending_at_i += alist[i]
        else:
            max_ending_at_i = alist[i]
            max_left_at_i = i
        if max_ending_at_i > max_seen_so_far:
            max_seen_so_far = max_ending_at_i
            max_left_so_far = max_left_at_i
            max_right_so_far = i + 1
    return max_left_so_far, max_right_so_far, max_seen_so_far


alist = input('Enter the list of numbers: ')
alist = alist.split()
alist = [int(x) for x in alist]
start, end, maximum = find_max_subarray(alist, 0, len(alist))
print('The maximum subarray starts at index {}, ends at index {} and has sum {}.'.format(start, end - 1, maximum))

Here are some example outputs:

Enter the list of numbers: 3 -2 4 -6 7 8 -10 4
The maximum subarray starts at index 4, ends at index 5 and has sum 15.

Enter the list of numbers: 4 5 -2 0 -5 15
The maximum subarray starts at index 0, ends at index 5 and has sum 17.

Enter the list of numbers: 3
The maximum subarray starts at index 0, ends at index 0 and has sum 3.

So I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

Answer 1

You should always handle edge cases. For instance, if one were to provide an empty list (or None) to your find_max_subarray() function, alist[start] would throw an IndexError.