Exercise 5.18 Consider the mar-sum problem: Given an array A of size n containing positive and negative integers, determine indices i and j, 1 sisi sn, such that A[i] + A[i+1] + ... + A[j] is a maximum. (a) Consider the array A = [5,10, 15, 20, -4,6,4,8, 10,20). Find the indices i and j that give the maximum sum and state the maximum sum. (b) Give a divide and conquer algorithm that runs in O(n log n) time. Assume, that adding or comparing two numbers takes constant time. (Hint: Split the array into two (almost) equal parts and recursively solve the problem on the two parts. The non-trivial part is combining the solutions note that it is possible that the indices i and j that give the optimal sum might be on opposite parts.)