How to calculate the best points to buy and to sell?

Question

There are pairs of buying and selling prices. For example:

101  99
100  98
102 100
105 102
101  99
...

I want to calculate maximum possible profit on historical data for the conditions: we buy and then we cannot buy until we sell it. Then we can buy again and then we can sell it again, etc. How can I calculate the solution with the best points to buy and to sell for getting maximum profit? (The amount of currency1 for buying currency2 is always the same).

Answer 1

Find the time $t_{s,max}$ with the maximum selling price (if there is a tie, take the latest point in time). Find the lowest buying price up to and including $t_{s,max}$. Buying at that lowest price and selling at the selling price of time $t_{s,max}$ is your first candidate transaction.

Now remove all buy/sell info at and before time $t_{s,max}$ and start this algorithm again. This will produce more candidate transactions, but will eventually finish as at least one line of buy/sell info is removed in each step. Take the transaction from the candidates that has the most profit (or don't do anything if that maximum profit turns out to be negative).

Then jump into your time machine and actually execute the transactions ;-)

In your example (if we assume it stops after line 101 99), $t_{s,max}$ would be step 4, the lowest buying price at or before that time is 100, so the first candidate becomes "buy for 100 at timestep 2 and sell for 102 at timestep 4".

After removing all data at and before timestep 4, we are left with only one more line, which becomes the next candidate: "buy for 101 at timestep 5 and sell for 99 at timestep 5".

After this, the algorithm ends as there is no mor buy sell info. So among the 2 candidates, the first one is the best.

Answer 2

Here is an illustrated algorithm which seems to work for discrete time intervals by buying the item when you will be able to sell it profitably later, and selling it either when there is an opportunity to buy it back more cheaply later or at the end when the price is falling, taking account of the inter-relationship between these:

1. Draw the prices

2. from each buy point, extend a horizontal line segment rightwards until you reach a time where the sell price is strictly greater

3. similarly from each sell point extend a horizontal line segment leftwards until you reach a time where the buy price is strictly lower

4. erase the buy horizontal lines where there are no sell horizontal lines strictly above them, and erase the sell horizontal lines where there are no buy horizontal lines strictly below them; the remaining indicated intervals are where you want to hold the item (i.e. buy at the beginning of the interval and sell at the end)