Problem 5: Consider the problem faced by a stockbroker trying to sel a large number of shares of stock in a company whose stock price has been steadily falling in value. It is always hard to predict the right moent to sell stock, but owning a lot of shares in a single company adds an extra complication: the mere act of selling many shares in a single day will have an adverse effect on the price Since future market prices, and the effect of large sales on these prices, are very hard to predict, brokerage firms use models of the market to help them make such decisions In this problem, we will consider the following simple model. Suppose we need to sell suppose that we have an accurate model of the market: it predicts that the stock price will take the values pi,P2 Pn over the next n days. Moreover, thereis a function f(y) that predicts the effect of large sales: if we sell y shares on a single day, it permanently decrease the price by f(y) from that day onward. So, if we sell y shares on day 1, we obtain a price per share of p-f() for a total income of y(p f()) Having sold shares on day 1, we can then sell y2 shares on day 2 for a price per share of P2-f(n)-f(p) this yields an additional income of ?? * (Pa-f(n)-f(p)). This process continues over all n days. (Note, as in our calton for day 2, that the decreases fro earlier days are absorbed into the r shares of stock in a company, and prices for a later days.) Design an efficient dynamic programming algorithm that takes the prices pi,. .. .Pn) and the functionf() (written as a list of values f(1), f(2), f(x) and determines the best way to shaes by day n. In other words, find natural numbers y, V2,.. .,Vn so that -i +...+, and selling y shares on day i for i 1,2,..., n maximizes the total income achievable. You should assume that the share value , is monotone decreas- ing, and f(r) is monotone increasing; that is, seling a larger nuber of shares causes a larger drop in the price. Your algorithm's ruing time can have a polynomial dependence on n (the number of days), (the number of shares), and Pi (the peak price of the stock) Example Consider the case when n = 3; the prices for the three days are 90, 80 40; and f(y) = 1 for y 40,000 and ,f(y) 20 for y > 40,000. Assume you start with -100, 000 shares. Se of them on day 1 would yield a price of 70 per share, for a total incoe of 7,000,000. On the other hand, seling 40,000 shares on day 1 yields a price of 89 per share, and sellng the remaining 60,000 shares on day 2 results in a price of 59 per share, for a total ncome of 7,100,000