Maximum Contiguous Subsequence Sum Problem. Let A[1..n] be an array of numbers. The elements in A can be either positive or negative. We want to find the indices k, l so that the sum P li=k A[i] is maximum among all possible choices of k, l. For example if A = {−3, 12, −6, 10, −5, 2}, the answer is k = 2, l = 4, since A[2]+A[3]+A[4] = 12 + (−6) + 10 = 16 is the maximum sum of all possible choices. It is easy to find an O(n2 ) time algorithm for solving this problem. Describe a divide-and conquer algorithm for solving this problem with run time at most O(n log n).

Answer rating: 100% (QA)

To solve the Maximum Contiguous Subsequence Sum Problem with a divideandconquer algorithm in On log ... View the full answer