Problem. Our goal is to buy and sell a given stock with maximum profit, assuming (not quite realistically) that we are able to predict the future. To be more specific, we assume we have an array P[1..n] (n 2 2) such that for each i 1.n, Pli] is the price (0) of the stock on day i; our goal is to compute an array A[1..n] of actions where each action is either NONE, BUy, or SELL. We require that such a sequence of actions is valid; that is the BuYs and SELLs are alternating: between two BuY actions there is always a SELL action, and between two SELL actions there is always a BuY action; we cannot sell before we buy: before a SELL action there is always a BUY action:; "cool down requirement": a SELL cannot be immediately followed by a BUY If a valid sequence has a BuY without any subsequent SELL we say that it is incomplete; otherwise it is complete. It is easy to see that an optimal valid sequence must be complete. As our running example, consider the prices In that case, an (the) optimal sequence of actions is 1 2 345 6 7 8 NONEBUY NONE SELL NONEBUY SELL NONE which will give a profit of (5-2) (3-2)-4. To solve this problem, we may try various approaches 1. (4p) An algorithm based on divide conquer. But it is not obvious how to do so: in our example, find the best valid sequence from Pl1.4] and the best valid sequence from P5.8], and then show that they can not be combined to form the best valid sequence from P[1.8] 2. (4p) The brute force approach where we examine all possible sequences (and choose the best) But this is infeasible show that the number of valid sequences is in ?(an) for some a > 1