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 A[i,j] with maximum sum, where 1ijn. More precisely, if s(i,j)=k=ijA[k]=A[i]+A[i+1]++A[j], denotes the sum of the subarray A[i,j], then we want to find the indices 1ijn such that s(i,j)=max{s(i,j):1ijn}. 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 maximum sum is s(i,j)=9 and is achieved for subarray A[3,6]=A[i,j]=[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