Best Time to Buy and Sell Stock with K transactions

Figure demonstrating the example listed in this article

Read the problem statement here.

Example: prices = [3, 2, 6, 5, 0, 3], k = 2

The key points mentioned in the problem statement are:
1. prices array contains the cost price of the stock on each day.
2. Maximum number of transactions is limited to k.
3. A stock can be bought only when there is no stock left to be sold.
4. Total profit needs to be maximized.

Let’s build the intuition:
1. On a particular day we can either buy a stock, or if we already own a stock then we can sell it, or else we don’t indulge in any kind of transaction (buy/sell).
2. Some storage space is required so that we can refer to it and find out what was the maximum profit we made till some i-1'th day, which will help us to calculate the maximum profit till the i’th day based on the previous point.
3. We may complete at most k transactions. So if we think sequentially starting right from one transaction and finding profit considering it to be the only transaction allowed for the entire span of days, then moving to at most two transactions and finding out the profit for all the days, using the previously computed profits. And finally reaching the point where we get the profit for at most k transactions.
4. Clearly a two-dimensional table is required, where the rows represent at most how many transactions may be done and the columns represent the number of days. Let’s name this table as dp. Each element of this table will denote the maximum profit possible by making at most k transactions till the i’th day.

5. Let’s initialize some base cases. If we can make zero transaction (k = 0) then we can’t make any profit, hence we fill the first row of the dp table with zeros. Similarly, when we have a single day to transact, we can’t complete a transaction, because we can’t buy and sell on the same day. Thus the first column of the dp table is also filled with zeros.
N.B.: The days follow 0 based indexing.

6. Now we need to sequentially fill in the first row (dp[1][1] to dp[1][5]) and the second row (dp[2][1] to dp[2][5]). For each cell (dp[k][i]) there are a couple of possibilities — no transaction on the i’th day or a transaction is completed on the i’th day. As we need to maximize the profit, we need to take the maximum between the two values.

dp[k][i] = max (No transaction on the i’th day, profit we can make by completing a transaction on the i’th day)
dp[k][i] = max (dp[k][i-1], prices[i] - prices[m] + dp[k-1][m])
// where m lies in the range 0 to i-1

Let’s break the above line into minimum meaningful subparts and analyze what it actually means:

dp[k][i-1]- If we aren’t doing any transactions on the i’th day, it means that the profit which we make till the i’th day for k transactions remains the same as what we make till the i-1'th day for k transactions.

prices[i] - prices[m] - It indicates 1 transaction, i.e. we are going to sell the stock on the current day (i’th day). Which obviously means we have definitely bought the stock on some day before the i’th day. Let’s assume that the day when we bought the stock as the m’th day. Now m can lie in the range 0 to i-1, because we are selling on the i’th day and we can’t buy and sell on the same day, hence m has to be some day before the i’th day.

dp[k-1][m] - We are allowed to do at most k transactions and we completed 1 previously (prices[i] - prices[m]), thus we are left with k-1 transactions. The stock which we sold on the i’th day was bought on the m’th day, which essentially means that we cannot engage in any other transaction from the m’th day to the i’th as because multiple transactions are not allowed simultaneously. Thus the k-1 transactions must be completed within m days. For this reason we add up dp[k-1][m] which gives us the maximum profit which we make by doing k-1 transactions till the m’th day.

7. The state dp[k][n-1] stores the maximum profit which can be obtained while transacting at most k times considering all the trade days. This is exactly what we’re looking for. Eureka !

Time Complexity: O(k*n²)
Space Complexity: O(k*n), where k is the maximum number of transactions allowed and n is the number of elements in the given prices array.

To check out the code click here.

Optimization of the above approach

We can avoid the repeated computations (iteration of m from 0 to i-1) while searching backwards in order to find the best day to buy the stock which is to be sold on the i’th day.

Let’s take the previous example as the reference. If we are computing the value for dp[2][4], it would be:

dp[2][4] = max(dp[2][3], prices[4] - prices[m] + dp[1][m])
where m ranges from 0 to 3

Showing each step as m ranges from 0 to 3

Again, If we are computing the value for dp[2][5], it would be:

dp[2][5] = max(dp[2][4], prices[5] - prices[m] + dp[1][m])
where m ranges from 0 to 4

Showing each step as m ranges from 0 to 4

Carefully observing the above two state computations it can be said that if we had already calculated the maximum of the values marked within the green box in the image below while calculating dp[2][4], we can simply find the maximum between it and the blue box in the image below in constant time, and avoid repetitive computations, while calculating dp[2][5].

Let’s rearrange our formula a bit to make it more readable:

dp[k][i] = max (dp[k][i-1], prices[i] - prices[m] + dp[k-1][m])
// where m lies in the range 0 to i-1
dp[k][i] = max (dp[k][i-1], dp[k-1][m] - prices[m] + prices[i])

As we’ve discussed the dp[k-1][m] - prices[m] part can be found out in constant time.
While calculating dp[2][1], the dp[k-1][m] - prices[m] part will be dp[1][0] - prices[0], as dp[1][0] is always 0, hence it is simply - prices[0] (let’s store this value in some variable, say maxDiff).
Now while calculating dp[2][1], the dp[k-1][m] - prices[m] part will be the maximum between maxDiff and dp[1][1] - prices[1].
Thus, instead of finding the maximum among all dp[k-1][m] - prices[m], where m ranges from 0 to i-1, we are finding maxDiff in constant time, which significantly reduces the overall computational time.

Time Complexity: O(k*n)
Space Complexity: O(k*n), where k is the maximum number of transactions allowed and n is the number of elements in the given prices array.

To check out the code click here.

Follow up question — Print all the transaction (buy & sell) days.

Figure demonstrating the backtracking process used to retrieve the stock buy and sell days

To check out the code click here.

Cheers !