Problem
Given is an array A of n integers. An ordered pair of A is a pair of integers (A (i, ALD) with i<-j. The maximum pair of A is an ordered pair, e.g., (A[J, ALl with i<-j, so that the difference A[] - Ali] is greatest among all ordered pairs in A. The goal is to design an algorithm to compute the maximum pair of A.
For examples, suppose A = {9,1, 5,4, 7) and then you should return "2, 5" (i.e., the maximum pair of A is (A[2], A[5); suppose A = {-7,2, -1, -10, -6} and then you should return *(1, 2)" (i.e., the maximum pair of A is (A [1], A [2])); suppose A = {8,7, 1, -4, -6} and then you should return any of "(1, 1)', "(2, 2)", "(3, 3)", "(4, 4", and "5, 5" lie.. the maximum pair of A is any of (8, 8), (7, 7), (1, 1), (-4, -4), and (-6, -6).
Design a divide-and-conquer algorithm to solve the problem in 0 (nlogn) time. Your algorithm should use the divide-and-conquer technique. Briefly present your idea first and then give the pseudocode. For your algorithm, please give the recurrence and the result.
No need to show how to solve the recurrence.