Problem 4 (Finding an Extreme Pair) 30 pts You are an adventurer hiking a new trail. For planning purposes, you want to find the stretch with the greatest greatest elevation gain. You have a data set that lists the altitudes of several mile markers along the trail. This data is available to you in the form of an array A1.n), where n is the number of markers and Ali) is the altitude of the ith mile marker. You wish to design an algorithm to determine the maximum of Alj] - Ali) over all pairs of mile markers 15). Here are a couple examples. For A = (2,1,4) , your algorithm must return the value of 3. For A = (4,2,1), your algorithm must return the value 0. If the trail is all downhill, then the maximum elevation gain is 0. For the questions below you need not give pseudo-code. A clear description as a sequence of well- specified steps will suffice. (5 pts) a Design an algorithm using a brute force approach. b State and briefly justify the time complexity of your brute force algorithm. 5 pts c Design an algorithm using a Dynamic Programming approach. Hint : Consider maintaining two variables - min-so-far and gain-so-far - and think about Bellman equations for updating them. (15 pts d State and briefly justify the time complexity of your algorithm. 16 pts)