(II)Complete the method of finding max diff() and analyze its running time.

 

Given an array A of n elements, find out the maximum difference between any two elements such that larger element appears after the smaller element in A. In other words, find a pair of elements A[p], A[q] with q>p such that (A[q] - A[p]) is the maximum among all such pairs in A. For example, if array is [2, 3, 10, 6, 4, 8, 1] then the maximum difference should be 8 (Diff between 10 and 2). If array is [ 7, 9, 1, 6, 3, 21 then the maximum difference should be 5 (Diff between 1 and 6). a divide-and-conquer algorithm of O(n) time complexity to solve this problem. (i) describe the idea behind your algorithm in English (2 points);