Difficulty: Hard
Category: Dynamic Programming
Step 1: Grasping the Problem
This problem gives an array of integer prices
denoting stock prices each day and an integer k
denoting the maximum number of transactions that can be made. We need to return the maximum profit possible for that stock. Some key points to notice in this problem is:
 There cannot be multiple simultaneous transactions. So there will not be any overlaps in the transactions.
 You can have at most
prices/2
transactions whereprices
is the number of days.  If
k > prices*2
, then it can be said that unlimited transactions can be made. Because you can make at mostprices/2
transactions as stated in the previous point.
This tells us that we may have to handle the scenario where k>price*2
and the normal cases separately.
The problem statement tells that we can do at most k
transactions, that means that we can have less than k
transactions. Notice that you can break any transaction to multiple transactions if that takes more that 2 days. Below is an example where prices = [2, 4, 5, 7]
. To get a profit of 7  2 = 5
, you can make two transactions: first one buying at day 1 and selling at day 3 (profit = 52 = 3
), and the second one buying at day 3 and selling at day 4 (profit = 75 = 2
). This gives a profit of 3 + 2 = 5
. And you can also do only one transaction buying at day 1 and selling at day 4.
Now suppose k=1
. In that case, you’ll need to check for only one transaction in the whole prices
and that would be the result. Then think of k=2
. We can do the following things at each day in that scenario:
 If we are not holding any transaction, then we can buy a new transaction. Buying means that we are subtracting the price of that day from our total amount. By this process, we can make at most
k
transactions.  If we are holding a transaction, we can sell a transaction: selling ith transaction means, the total amount becoming the the last time we gave money to buy a transaction plus the price of today’s stock.
So, we can track all the states of the transactions and prices by tracking our total amount for each buy and sell, making new transactions by adding or subtracting todays price from the last transaction.
This gives us intuition about the problem being a DP (Dynamic programming) problem. Here, we will use two arrays to store the maximum amount possible at each transaction. We do not need to track this based on days, because only the transactions make changes to those states.
buy[t] : Amount of money while buying for the t'th transaction.
sell[t]: Amount of money while selling for the t'th transaction.
Step 2: Create a DP table
DP (Dynamic Programming) is a programming paradigm where there can be multiple dependent subproblems. There are two different ways to approach a DP problem: Recursively and iteratively. We will be showing the iterative approach as it can be elaborated more with data. For iterative Dynamic Programming, you will need to fill up a table which is known as DP table. As our problem is only dependent on the last transaction from the current transaction, and there are at most k
transactions possible, we will use a DP table of k*2
size, where the first row of the table is the track of best buy transaction amounts, and the second row is track of best sell transaction amounts. Now the initial values of the buy row will be a minimum value, so that we can compute them with a negative value. We will need this in future. On the other hand, sell row will be initialized to zero because, without making any transactions you’ll get total amount of zero.
transaction  1  2  …  k 

buy  ∞  ∞  ∞  ∞ 
sell  0  0  0  0 
This can be done either by creating a 2D array, or buy creating just two variable buys
and sells
. Multiplying an array with an integer in python will result in concatenating the array with itself. We can use this to initialize the value.


Step 3: Fill up DP table
As we have defined how we are going to store the states needed for the problem, we will need a state transition function. We will do this by first iterating through the prices
stock prices list, and then iterating through the number of transactions we can make at most.


Initially when we do not have any transactions done, the price will be price
where price
is the price of the first day. This will be negative so that when we sell this stock, the price will be new_buy = price(at day 1) + price(at day of selling)
. Of course the selling price will have to be greater than the buying price so that we can make a profit. We will use a new variable new_buy
to store this.


Now what will be the amount when it is not the first transaction? Then we will already be having a profit in our hand. And this value will be in the sells row’s last transaction column (sells[transaction  1]
). Then we will subtract todays price
from that value.


Now that we have got the value we need for what happens if we buy a transaction or not, we can update the buys
row. We will only buy if it is beneficial than not buying the transaction.


After updating the buy for current transaction
, We will see if we can sell beneficially today. We will sell today only if it is profitable, meaning adding todays stock price to the last buys[transaction]
becomes greater thatn sells[transaction]
.


In most of the languages, the above two updating can be done in one line with the help of builtin max
function.


After filling up the table, for example with prices = [5, 11, 3, 50, 60, 90]
and k = 2
, the table will look like below.
price  transaction  buys  sells 

5  0  [5, inf]  [0, 0] 
5  1  [5, 5]  [0, 0] 
11  0  [5, 5]  [6, 0] 
11  1  [5, 5]  [6, 6] 
…  …  …  … 
60  0  [3, 3]  [57, 53] 
60  1  [3, 3]  [57, 63] 
90  0  [3, 3]  [87, 63] 
90  1  [3, 3]  [87, 93] 
Step 4: Handling corner cases
There can be two corner cases for this problem.
 The typical corner case: What if you have no stock prices?
prices = 0
. What happens if you can make 0 transactions?k = 0
. In both of these scenarios, we can tell that we will have a maximum of 0 profit. So we return0
.


 Unlimited transactions: As we have already stated in Step 1, you can have at most
prices*2
transactions? So what ifk > prices*2
? Then you can easily calculate assuming you have unlimited transactions.


Note that these cases should be handled before going for the actual DP generation. Because there is no need to have a DP table if you already know you can have unlimited transactions.
Step 5: Returning the result
At this point, we have the DP table filled up properly. So what we can do is return our profit at k
‘th transaction. We know that our profit is saved in sells
row. So returning the k
‘th column of it will be sufficient.


The overall program is given below. As we had to loop through the prices
list and number of transactions (k
), the time complexity will be O(prices * k)
. The space complexity will also be O(prices * k)
for the DP table.





