1 Suppose we drive a pickup truck from city A to city B. Along the high way, we will go through n apple markets, labeled with 1, 2, ..., n, where you can buy or sell apples. City A and city B also have an apple market each. For convenience, we label city A with 0 and city B with n+1. From a customer point of view, the buying price B[i] and selling price S[i] (dollar per pound) at market i are known. An example with n = 4 is given below.

Now, we will stop at one of the stations to buy apples and then stop at another station to sell apples. Please design an O(n) greedy algorithm to find market i to buy apples, and find market j ? i to sell apples such that the profit will be maximized. We assume that it would be too costly and forbidden to drive backward. In the above example, the best result is to buy apples at market 3 and sell them at market 5 with profit of (7-2 = 5) dollars per pound. It is allowed that i = j which means you buy and sell apples at the same market i.

Also Design a divide and conquer algorithm to solve problem 2. The time complexity of your algorithm must be O(nlgn) or better.