Question

(13 pts) Given an array AlI,2,. .. ,n] integers, design and analyze an efficient Divide-and-Conquer algorithm to find some i and j, where j > 1, such that A[j]-Ali] is maximized. For example, given A 6, 1,3,8,4,5, 12,6], the maximum value of AL] - Ali] for j > i is 12-1 11 where j -7 and i 2. Give the underlying recurrence relation for your algorithm and analyze its running time. You should carefully state all details of your algorithm: How to divide, what each recursive call returns, and how the information is used in each step.

Answer 1

`Hey,

Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries

Divide and Conquer

1. We need to find the two elements A[i] and A[j] so that A[j] – A[i] is maximum and j > i
2. Divide the input array into 2 parts, left Half and right half.
3. We have divided the problem in 2 parts. Now we can conclude that for answer-
   1. Both indexes i and j are in the left half of the array.
   2. Both indexes i and j are in the right half of the array.
   3. Index i is in left half and index j is in right half of the array.
4. Solve the above 3 sub problems recursively and final answer will the maximum of these 3 sub problems.
5. This solution is very much similar to Merge sort

Time complexity is O(nlogn).

Kindly revert for any queries

Thanks.