Hello Friends, if you are into solving Data structure and algo problems. You might have come across this problem to get the Max Profit with k transaction. If you don’t get the core concept and logic to solve this problem, it would be very difficult to solve it.
In this article I would like to walk you through the problem and the logic behind its solution. The sample code is in C# but you can convert to any programming language like Java, C++ or Python.
Problem Statement:
You’re given an array of positive integers representing the prices of a single stock on various days (each index in the array represents a different day). You’re also given an integer k, , which represents the number of transactions you’re allowed to make. One transaction consists of buying the stock on a given day and selling it on another, later day.
Write a function that returns the maximum profit that you can make by buying and selling the stock, given k transactions.
Note that you can only hold one share of the stock at a time; in other words, you can’t buy more than one share of the stock on any given day, and you can’t buy a share of the stock if you’re still holding another share. Also, you don’t need to use all k transactions that you’re allowed.
Sample Input: prices = [5, 11, 3, 50, 60, 90], transactions = 2
Sample output : 93
In this example, the first transaction would be to buy at 5 and sell at 11, and again to buy at 3 and sell at 90.
Solution
We can solve this problem using the dynamic programming. The reason we can solve it using dynamic programming is that we can create solution of less number of transactions and use it to build the solution for more number of transactions.
Lets start with the explanation.
Always remember that while solving any dynamic programming problem, we always need to have the base case.
In this scenario, the base case would be if we are not doing any transaction. As you can see in the figure below, the columns are the days with the share price and rows are the transaction number. And cell contains the profit value.
Suppose if we are not doing any transaction, in that case our profit will be always zero.
Now we want to get the profit with one transaction. To get the profit we need to substract the current days price with the minimum in previous days.
On the first day, since there would not be any way to buy if earlier that first day, the profit would be 0.
On the second day, we can sell it for 11 but we can buy only for 5. The profit is 6.
On the third day, with stock price of 3, we would not be able to make any profit as there is no day with price lesser than 3. We will carry the profit from previous day i.e. 6.
On the fourth day, with stock price of 50, we can make max profit if we buy at 3 and sell at 50 i.e. 47. We need to find the minimum buy price from previous days and substract from current day.
And you can fill the remaining profits.
Still we are not at a formula which can solve the problem with more transactions.
Second Transaction
Hope you are able to understand the problem till now. Lets start with a bit more complex scenario. Please stay with me and I shall be able to explain you the solution.
In the figure above, I have included the max profit for the second transaction. How do I come there values? Let’s try to understand.
If I want to find the maximum profit for the fourth day and second transaction i.e. the price of the stock is 50. The max profit could be either the max profit of the previous day or adding the profit from the previous days on previous transaction.
We will take the profit from the previous day for forth day i.e. 6. And if we want to do a second transaction, we will be selling our stock for 50, plus we have to get the maximum profit from previous days. In this case it will be 3.
To get the maximum profit from previous days, substract the price on that day from the existing profit. For first day the max profit is 0 and buying price is 5. The max profit is -5.
Similarly its again -5 and 3 for second and third days. And the max profit from the first transaction till fourth day is 3. Add the current day price to max profit. And we get the max profit of 53. We will get the maximum of 6 and 53. Its 53.
That’s how we calculate the max profit for fourth day.
Similarly you can calculate the max profit for all the days using this logic.
Solve the problem programmatically
Lets have a look at the code solutions for the problem
public static int MaxProfitWithKTransactions(int[] prices, int k) { int[,] profits = new int[k + 1, prices.Length]; for (int t = 1; t < k + 1; t++) { int maxThusFar = Int32.MinValue; for (int d = 1; d < prices.Length; d++) { maxThusFar = Math.Max(maxThusFar, profits[t - 1,d-1 ] - prices[d -1]); profits[t, d] = Math.Max(profits[t, d - 1], prices[d] + maxThusFar); } } return profits[k, prices.Length - 1]; }
I will make the code more clear with step by step explanation:
- Create a 2D array with rows as number of transaction plus one as we will keep the first row for no transaction. Number of columns would be the number of days or prices.
- We will traverse the 2D array and start with the max profit so far as minimum value. maxThusFar contains that value.
- Get the max profit from the previous transaction. We will get it by substracting the previous days profit from the price and check if is greater than existing profit.
- Store the price in the matric item, greater of the previous days profit or the value from the previous step.
- Get the max profit from the value present in the last cell.
Conclusion
Max Profit with k transaction is a classic problem of dynamic programming. Here we divided the problem in smaller sub problems by getting the profit for lesser number of transactions. Using these results to solve the bigger problem.