## I am trying to find an efficient algorithm that takes the prices p1 . . . pn and the function values f (1) . . . f (x) and determines the best way to sell x shares by day n.

Problem set-up.

I’m given the market prices for this stock over the next n days, let these be p1, p2 …pn. I also know the function f(y) which predicts the effect of selling y shares on a single day: if you sell y shares, it permanently decreases the price of the stock by f(y) from that day onwards.

So, if I sell y1 shares on day 1, the price per share for the transaction is p1 −f(y1) and the corresponding profit for that day is y1 · (p1 − f(y1)). If I then sell y2 shares on day 2, the price per share for that transaction is p2 − f(y1) − f(y2). Note that the decreases in price accumulates.

Assume that p1 …pn decreases monotonically and f(1) …f(x) increases monotonically. (Prices are generally going down and it goes down even more if I sell more shares). I can also assume that no matter how I sell your stocks, it is impossible for me to reduce the price of the stock to 0 (or negative numbers). (meaning, pi is larger than the cumulative decrease in price from any possible sequences of sales in the first i days) In other words, the algorithm finds integers y1 . . . yn, where yi corresponds to the number of shares sold on day i, such that:

- All x shares are sold: ni = 1 yi = x.
- The total profit is maximized.