This is a Python program to solve the maximum subarray problem using Kadane’s algorithm.

The program finds a subarray that has the maximum sum within the given array.

1. Define the function find_max_subarray that takes a list as argument and two indexes, 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, r are the left and right indexes 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, right indexes as the loop iterates.

Here is the source code of a Python program to find the subarray with maximum sum. The program output is shown below.

def find_max_subarray(alist, start, end): """Returns (l, r, m) such that alist[l:r] is the maximum subarray in A[start:end] with sum m. Here A[start:end] means all A[x] for start <= x < end.""" max_ending_at_i = max_seen_so_far = alist[start] max_left_at_i = max_left_so_far = start # max_right_at_i is always i + 1 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))

1. The user is prompted to enter a list of numbers.

2. The list is passed to find_max_subarray and the returned tuple is stored.

3. The start and end indexes and the sum of the maximum subarray is printed.

Case 1: 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. Case 2: 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. Case 3: Enter the list of numbers: 3 The maximum subarray starts at index 0, ends at index 0 and has sum 3.

**Sanfoundry Global Education & Learning Series – Python Programs.**

To practice all Python programs, __here is complete set of 150+ Python Problems and Solutions__.