Part B: 9. Maximum sum subarray problem is the following problem: We are given an array A[1..... n) of integers (positive and negative), and the goal is to compute a subarray Al/./] with maximum sum, where 1 si si sn. More precisely, if s(i.) A[k] A+ A[+1]++ AU]. k denotes the sum of the subarray Ali.], then we want to find the indices 1 sssn such that s(i,j) max(s(i,j): 1iin). For example, if n = 8 and A[1,2,3,4,5,6,7,8] = [3,-4,6,-1,-1,5,-3,2], then the maxi- mum sum is s(i,j)-9 and is achieved for subarray A[3,6]-A[./]-[6,-1,-1,5]. (a) [5 marks] Design a divide and conquer algorithm that solves this problem in time O(nlogn). (b) [4 marks] Give an argument that your algorithm indeed has running time O(nlogn) by formulating an appropriate recurrence equation and solving it