Computing Max Diff

Assume you can somehow foresee stock price for, say 1000 days, from today. If you are given, say k, chances to buy and sell those stock at all different days, how would you calculate the maximum profit you could get? Assume that you can only hold max 1 share at a time, so you won't be able to buy, buy, buy, and sell, sell, sell. You will need to buy, sell, buy, sell, ... and so forth.

For example, consider the daily price to be x_i = {4005 1330 6570 4925 7112 6182 177 1843 2897 5557 8561 5875 7069 6192 4358 8624} for i=1,2,..,16. If you are given 3 chances each to buy and sell this stock at each different day, what would be the maximum profit?

One way would be to buy at x_1, x_3, x_5 while selling at x_2, x_4, x_6, but this probably won't get you the maximum profit.

This is the classical max difference problem. Let's see how we can solve this.

As with any other algorithm problem, you should start looking for some sort of recursive relationship. Define

S(n,k) = max profit you would get by buy-sell k times with the last sell at x_n.

For example, S(3,1) would be x_3 - x_2, and S(5, 2) would be x_3 - x_2 + x_5 - x_4

It is not easy to instantly find the relation between S(n,k) and S(n-1,k) or S(n,k-1) or S(n-1,k-1). We need some helper variable. Define

B(n,k) = max cash you would get by buy-sell k-1 times before x_n, and buying kth time at x_n.

For example, B(1,1) would be -x_1, which is the only option. B(2,1) would be -x_2, and B(6,3) would be  x_3 - x_2 + x_5 - x_4 - x_6.

Now, we see the recursive relation between B and S:

B(n,k) = max[S(i, k-1)] - x_n for i<n
S(n,k) = max[B(i,k)] + x_n for i<n

OK, does that mean we need to store B and S 2D-arrays and find max for each (n,k)? Well, one way to avoid this is to instead store maxB and maxS 2D-arrays and store the max value up to n. For example, maxB[n][k] will be the max of B(1,k) through B(n,k).

The following is the source code for this.


Note that this requires O(n*k) space, which could be quite a lot. To reduce this, notice how maxB[i][k] and maxS[i][k] are of no usage for n>i+1. Therefore, at the end of each loop in n, we can update maxS and maxB and overwrite. In this way, we can store maxB[k] and maxS[k] 1-D arrays.

The following is the source code for this.


There is one little catch here though. We must loop through k in descending order, so that getS and getB functions access maxS and maxB from the previous loop in n, not the newly updated in the current loop in n.