Given an array of temperatures t1, . . . , tn measured on n days, the weather service would like to compare the biggest increase in temperature to the biggest decrease in temperature over the given period. Specifically, you would like to compute two numbers: (a) maxup, the maximum over pairs i < j of tj ti and (b) maxdown, the maximum over pairs i < j of ti tj

. For example, for the array [10, 0, 1, 2, 3, 4, 1],

you would compute maxup = 4 and maxdown = 11. (a) (10 points) Give a divide and conquer algorithm that computes these numbers in O(n) time. [Hint: Cut the array into two and make a recursive call on each half. It may be helpful to have the recursive calls pass up some extra information (in addition to maxup and maxdown).]

(b) (10 points) Give a linear-time algorithm for the same problem which makes a single pass through the data and uses only a constant amount of workspace (beyond the space needed to store the input).