This is a Python program to solve the maximum subarray problem using divide and conquer technique.

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 base case is when the input list is just one element (i.e. start == end – 1).

4. Otherwise, the list is divided into two and find_max_subarray is called on both the halves.

5. The maximum subarray is either the maximum subarray of one of the halves or the maximum subarray crossing the midpoint of the two halves.

6. The function find_max_crossing_subarray takes a list as argument and three indexes, start, mid and end and finds the maximum subarray containing mid.

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.""" # base case if start == end - 1: return start, end, alist[start] else: mid = (start + end)//2 left_start, left_end, left_max = find_max_subarray(alist, start, mid) right_start, right_end, right_max = find_max_subarray(alist, mid, end) cross_start, cross_end, cross_max = find_max_crossing_subarray(alist, start, mid, end) if (left_max > right_max and left_max > cross_max): return left_start, left_end, left_max elif (right_max > left_max and right_max > cross_max): return right_start, right_end, right_max else: return cross_start, cross_end, cross_max def find_max_crossing_subarray(alist, start, mid, end): """Returns (l, r, m) such that alist[l:r] is the maximum subarray within alist with start <= l < mid <= r < end with sum m. The arguments start, mid, end must satisfy start <= mid <= end.""" sum_left = float('-inf') sum_temp = 0 cross_start = mid for i in range(mid - 1, start - 1, -1): sum_temp = sum_temp + alist[i] if sum_temp > sum_left: sum_left = sum_temp cross_start = i sum_right = float('-inf') sum_temp = 0 cross_end = mid + 1 for i in range(mid, end): sum_temp = sum_temp + alist[i] if sum_temp > sum_right: sum_right = sum_temp cross_end = i + 1 return cross_start, cross_end, sum_left + sum_right 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 4 -2 3 -10 32 4 -11 7 -3 2 The maximum subarray starts at index 5, ends at index 6 and has sum 36. Case 2: Enter the list of numbers: 4 -2 3 4 1 4 -5 The maximum subarray starts at index 0, ends at index 5 and has sum 14. Case 3: Enter the list of numbers: 2 The maximum subarray starts at index 0, ends at index 0 and has sum 2.

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

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