Algorithms - optimal way to buy and sell a stock over an interval
Someone gave me a problem from a textbook that I can't figure out. It is:
Let's say that you have a stock STOK that you are set on investing all of
your money in for a month (days 0...30), and at the end of the month you
can't hold any of the stock. You have m money. For any day d the price of
STOK is p(d), and on any day you can either buy or sell stock. However,
there is a limit, l(d), to how much stock you can buy and sell in one day
(it's the same for buying and selling). You can buy non-integer units of
stock if you want, for ease of calculation. Given these functions, how do
you schedule a purchase plan to maximize your profit?
The naive solution: Every day buy as much stock as you can under the
following constraints: If you are unable to sell all of your stock by the
sell date do not buy any more; If you are out of money, do not buy any
more. When you reach the point where you must begin selling stock (this is
known, for you know the stock prices in advance) then sell as much as you
can every day. This solution doesn't work, however, because what if the
stock dips at the beginning of the month then soars after the first five
days?
This smells like dynamic programming, but the fact that the stock price
isn't monotone makes it hard. Brute force is clearly out given the
continuous nature of the problem. Any solutions?
No comments:
Post a Comment