LeetCode – Best Time to Buy and Sell Stock IV Answers/Solution/Thoughts

This is the generic version of following problems
Best Time to Buy and Sell Stock III (two transactions)
Best Time to Buy and Sell Stock II (unlimited transactions)
Best Time to Buy and Sell Stock (one transaction)

So there are two dimensions to be considered: the number of transactions and the profit up to a given point of time. First let’s consider the case when k = 1, for every new day i we will have to decide:

1. localProfit(i) = price(i) – price(x)  –x will be the min price day which earlier than day i; –consider case 54389 at 9, localProfit = 6
2. or localProfit(i) = price(i) – price(i – 1)  –consider case 54389 at 8, localProfit = 5
3. or localProfit(i) = localProfit(i – 1)  –consider case 54389 at 3, localProfit = 0

All these cases’ result will depend on if we already have the min number, which can be calculated by:

margin = prices(i) - prices(i - 1)
localProfit[i] = localProfit[i - 1] + margin

if margin > 0, we will get case 1 if there is a min value before day i, case 2 if day i is the first increasing day.
if margin <= 0, we get case 3.

Next we need to deal with another dimension K.
Basically there will be a limit of maximum profit before specific day. Say case 54389, before “3” no matter how many transaction you have you will have to “waste” it.
So before we reaching the limit, everytime we increase the number of trans, say “X”, we made before a specific day, it will be based on result for “X – 1”.

For every new day we decide:

1.Do we make the last trans between price(i) and price(i – 1)? If we do, we calculate the best on a day before with last trans to be done:

globalProfit[i - 1][k - 1] + (margin > 0 ? margin : 0)

The reason why we do this is because we could have best profit detached from day i – 1: case 14876 on 6, best profit with k = 1 is 7, margin = 0;

2.Should we calculate current profit using price(i) – price(x) (x is min price day earlier than i, keep last trans open and close on day i)

localProfit[i - 1][k] + margin

3.Calculate best localProfit.

4.Compare best localProfit[i][k] to globalProfit[i – 1][k].
If day i is the highest point so far, last trans will be made from last valid min prices day(could be i – 1) to day i, which is localProfit[i][k]
Here “last valid min prices” means we uses all k – 1 trans to get most of the value before day i – 1, like Best Time to Buy and Sell Stock II (unlimited trans). The next min point will be valid min prices.

If not, that means prices(i) < prices(i – 1), we take globalProfit[i – 1][j] instead.

margin = prices[i] - prices[i - 1];
localProfit[i][j] = Math.max(globalProfit[i - 1][k - 1] + (margin > 0 ? margin : 0), localProfit[i - 1][k] + diff);
globalProfit[i][j] = Math.max(localProfit[i][j], globalProfit[i - 1][j]);