Need to design an algorithm for the problem by using dynamic programming.

Selling shares of stock (KT 6.25) Consider the problem faced by a stockbroker trying to sell 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 moment 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 x shares of stock in a company, and suppose that we have an accurate model of the market: it predicts that the stock price will take the values p_1, P_2, .., p_n over the next n days. Moreover, there is a function (middot) that predicts the effect of large sales if we sell y shares on a single day, it will permanently decrease the price by f(y) from that day onward. So, if we sell y_1 shares on day 1, we obtain a price per share of p_1 - f(y_1), for a total income of y_1 middot (P_1 - f(y_1)). Having sold y_1 shares on day 1, we can then sell y_2 shares on day 2 for a price per share of p_2 -f(y_1)- f(y_2): this yields an additional income of y_2 middot (p2-f(y_1)-f(y_2)). This process continues over all n days. Design an efficient algorithm that takes the prices p_1, ..., p_n and the function f(middot) (written as a list of values f(1), f(2), .., f(x)) and determines the best way to sell x shares by day n. In other words, find natural numbers y_1, y_2, ..., y_n so that x = y_1 + + y_n, and selling y_i shares on day i for i = 1, 2, ..., n maximizes the total income achievable. You should assume that the share value p_i is monotone decreasing, and f(middot) is monotone increasing: that is, selling a larger number of shares causes a larger drop in the price. Your algorithms running time can have a polynomial dependence on n (the number of days), x (the number of shares), and p_1 (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 lessthanorequalto 40,000 and f(y) = 20 for y > 40.000. Assume you start with x = 100,000 shares. Selling all of them on day 1 would yield a price of 70 per share, for a total income of 7,000,000. On the other hand, selling 40,000 shares on day 1 yields a price of 89 per share, and selling the remaining 60,000 shares on day 2 results in a price of 59 per share, for a total income of 7, 100,000