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

## No comments:

## Post a Comment