Let A[1n] be an array of n positive and negative numbers. The k-maximum subarray of A is a contiguous subarray of size no more than k which has the largest sum. For example, the given array is {4, -3, 6, -2, 1, 4, -8, 9, -10, 2} and k=2, the 2-maximum subarray of A is {9} and the sum is 9; if k=6, the 6-maximum subarray of A is {4, -3, 6, -2, 1, 4} or {6, -2, 1, 4, -8, 9} and the sum is 10. Please give an algorithm to compute the sum of the k-maximum subarray of A in O(nk) time. Note when k is linear in n, O(nk) is bounded by O(n2). Please improve the above algorithm to O(nlog n) time by designing a divide-and-conquer algorithm to compute the sum of the k-maximum subarray of A. Please briefly describe the main idea of your algorithms and analyze their time complexities. You will receive the full 30 points if you give an O(nlog n) time algorithm directly for (b) without giving any algorithm for (a).