This one is pretty similar to #297. When we are buying for the second time, we are removing from the profit earned from the first transaction. So, instead of subtracting the price from 0, we subtract it from the first transaction profit and then add on to it when we are selling. So, we just need two more variables.
Here, there are 3 approaches. The dynamic programming one sounds more familiar, so I will explain it first:
1. Dynamic Programming
When we are deciding for the i-th transaction at j-th price, it's pretty easy to derive a recursive formula:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[h] + prices[j]), where h<j.
This is semantically equivalent to saying "The maximum profit for some transaction at some index is equivalent to the maximum of either not making any new transactions at that index or the maximum profit at the previous transaction in some previous index added with profit of some new transaction where we sell at some index.". "Some previous index" can be decided linearly by comparing the maximum for the expression dp[i-1][j-1] - prices[h] for all indices up to j.
2. Valley-Peak Merging
When we look at the graph of some prices, we see local minimum and maximums.
When the given number k is less than the number of valley-peak pairs, we have to exclude some of those. In the graph above, if we were only allowed a single transaction, we would have chose the fist price to buy and the last to sell, merging the valley and the peak, excluding those in-between.
Think of some prices like this: [1,7,5,12], where k = 1
The best choice here is 1|12 yielding 11 profit. If we did two transactions with 1|7 and 5|12, we would have earned 13, exactly 7-5 more than the previous one. The reason is, when k is 2, profit is p2 - v2 + p1 - v1. When k = 1, profit = p2 - v1. That is how that increment comes. So, if needed, we pick the largest range value. We include the second value by including the profit from p1 - v2. This also holds for 3 or more transactions, when their profits overlap. p3 - v3 + p2 - v2 + p1 - v1 => pick p3 - v1, pick p2 - v3, pick p1 - v2 etc. We can put all the profits into a priority queue and just poll them. This algorithm should be faster in theory with linearithmic time in comparison to DP's pseudo-quadratic complexity, but it's slower in implementation.
3. Binary Searching
The procedure used for solving #369 and #368 can be used for this problem too.
We can actually sort out at which prices we sell by placing a lower boundary for it. We then count how many transactions are done with this lower bound. If the number exceeds k, we need to increase the lower bound, else, we need to decrease to earn more profit. This binary searching approach is the fastest.
Like their prequels, these problems are dynamic programming problems.
123. Best Time to Buy and Sell Stock III
Problem: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
This one is pretty similar to #297. When we are buying for the second time, we are removing from the profit earned from the first transaction. So, instead of subtracting the price from 0, we subtract it from the first transaction profit and then add on to it when we are selling. So, we just need two more variables.
188. Best Time to Buy and Sell Stock IV
Problem: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
Here, there are 3 approaches. The dynamic programming one sounds more familiar, so I will explain it first:
1. Dynamic Programming
When we are deciding for the i-th transaction at j-th price, it's pretty easy to derive a recursive formula:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[h] + prices[j]), whereh<j. This is semantically equivalent to saying "The maximum profit for some transaction at some index is equivalent to the maximum of either not making any new transactions at that index or the maximum profit at the previous transaction in some previous index added with profit of some new transaction where we sell at some index.". "Some previous index" can be decided linearly by comparing the maximum for the expressiondp[i-1][j-1] - prices[h]for all indices up toj.2. Valley-Peak Merging
3. Binary Searching
The procedure used for solving #369 and #368 can be used for this problem too. We can actually sort out at which prices we sell by placing a lower boundary for it. We then count how many transactions are done with this lower bound. If the number exceeds k, we need to increase the lower bound, else, we need to decrease to earn more profit. This binary searching approach is the fastest.