2

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).

user1034253
  • 121

2 Answers2

1

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

enter image description here

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

enter image description here

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

enter image description here

  1. 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)

enter image description here

Henry
  • 157,058
  • Thanks! But what we need to in this case https://imgur.com/a/N8YeMiQ ? – user1034253 Aug 13 '18 at 18:24
  • @user1034253 I think your link suggests an extra high sell point at time $4.5$ of $102.5$ so with an extra yellow line there extending backwards to time $3$ so then the green line at $102$ will extend to from $2$ to $4.5$ and have yellow above and so this algorithm will tell you to buy at $2$ and sell at $4.5$ (and $7$ to $9$ as before) – Henry Aug 13 '18 at 23:35
0

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.

Ingix
  • 14,494
  • I meant that buys and sells can be made many times during this data history. Is your answer takes this into account? – user1034253 Aug 13 '18 at 10:53
  • But you can only buy at each time in point once and sell only once, or what are the restrictions? – Ingix Aug 13 '18 at 14:39
  • I mean if we have data like here https://pastebin.com/nNUeQ2th this algorithm gives us the same 4 points like there? – user1034253 Aug 13 '18 at 14:51
  • You have to specify the exact conditions on what is possible/allowed to have any chance of getting a meaningful answer. For example (assuming each line represents a day), can you buy the first 3 days, then sell on days 7, 8, 9? Or can you only hold one of those things that you are buying? Or maybe 2? I'm not a mindreader, the multiple buy/sell thing was something that wasn't clear to me, and I don't know how much else you take for granted and don't write about. – Ingix Aug 13 '18 at 14:56
  • Edited the question. – user1034253 Aug 13 '18 at 15:05
  • Thanks, will think about it. – Ingix Aug 13 '18 at 15:08