You are consulting for a small investment company. They give you the price of Googles shares over the last n days. Let S[1 . . . n] be the array of share prices, where S[1] is the price of the stock on the first day in this time period. During this window, the company wanted to buy a fixed number of shares on some day and sell all these shares on some later day (that is, only one purchase and one sale). The company wants to know when they should have bought and when they should have sold in order to maximize their profit. If there was no way to make money during the n days, you should report Impossible.

For example, if n = 3 and S = [9, 1, 5], then you should return buy on day 2 and sell on day 3.

Your goal is to design a divide-and-conquer algorithm for this problem that runs in time O(n log n).

(a.) In one sentence, describe a simple algorithm for this problem that takes O(n 2 ) time.

(b.) Use the same divide strategy as merge sort. Consider two cases: (1) there is an optimal solution in which the investors are holding the stock at the end of day n/2, and (2) there is no such optimal solution. For each case, express the optimal solution in terms of something you can compute on the two subarrays. Give a brief explanation and pseudocode for your algorithm.

(c.) Analyze the running time of your algorithm.

(d.) How could we improve this algorithm to O(n)? (Do not fundamentally change the approach from Divide & Conquer)