# Python Program to Solve Maximum Subarray Problem using Kadane’s Algorithm

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

Problem Description

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

Problem Solution

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.

Program/Source Code

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))```
Program Explanation

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.

Runtime Test Cases
```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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]