For our final problem, we will practice solving an algorithmic problem using the method of divide and conquer. Once again, we will work on a classic: the maximum subarray problem. You are given array of integers (they can be negative) and you need to discover two indices into the array (left and right) such that the sum of the numbers in the array between index left and index right is the maximum you can obtain with that array.

For example, consider the array A = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7] If left = 3 and right = 5, the sum is A[3] + A[4] + A[5] = 20 + (-3) + (-16) = 1 If left = 10 and right = 11, the sum is A[10] + A[11] = 12 + (-5) = 7 So, the sum between indices (3,5) is greater than the sum between indices (10,11).

In this example, the subarray with the maximum sum is for left = 7 and right = 10, with a sum of 43.

Of course, we could consider every pair of possible left and right indices, which would lead of O(n * n) summations and comparisons (you should make sure that this is indeed obvious to you!).

Following is an implementation of this naive function for your reference. Your goal is use the divide and conquer method to devise and implement an O(n log n) solution.

def maxSubArray(arr): n = len(arr) max_sa = arr[0] left = 0 right = 0 for i in range(n): acc = 0 for j in range(i,n): acc += arr[j] if acc > max_sa: max_sa = acc left = i right = j return (max_sa,left,right)

example = array.array('i',[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7])

maxSubArray(example)

Output:

(43, 7, 10)

**Problem 8. (30 points): use the divide and conquer methodology to design and implement a solution to the maximum subarray problem in O(n log n) comparisons in the worst-case for an input array of size n.**

def maxSubArrayDC(arr): isinstance(arr,array.array) pass