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 where |prices| 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 most |prices|/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 = 5-2 = 3), and the second one buying at day 3 and selling at day 4 (profit = 7-5 = 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:

1. 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.
2. 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.

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.

1
2
3

# Build the table
buys  = [float('-inf')] * k
sells = [0            ] * k

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.

1
2

for price in prices:
    for transaction in range(k):

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.

1
2

if transaction == 0:
    new_buy = -price

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.

1
2

else:
    new_buy = sells[transaction-1] - price

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.

1
2

if new_buy > buys[transaction]:
    buys[transaction] = new_buy

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].

1
2

if buys[transaction] + price > sells[transaction]:
    sells[transaction] = buys[transaction] + price

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

1
2

buys[transaction] = max(buys[transaction], new_buy)
sells[transaction] = max(sells[transaction], buys[transaction] + price)

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

Step 4: Handling corner cases

There can be two corner cases for this problem.

1. 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 return 0.

1
2
3

# Corner cases 1: Usual
if not prices or k == 0:
    return 0

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

1
2
3
4
5
6
7
8

# Corner case 2: unlimited transactions
if k >= len(prices)/2:
    profit = 0
    for price_index in range(len(prices)-1):
        new_profit = prices[price_index+1] - prices[price_index]
        if new_profit > 0:
            profit += new_profit
    return profit

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.

1

return sells[k-1]

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def maxProfit(self, k: int, prices: [int]) -> int:
        # Corner cases 1: Usual
        if not prices or k == 0:
            return 0

        # Corner case 2: unlimited transactions
        if k >= len(prices)/2:
            profit = 0
            for price_index in range(len(prices)-1):
                new_profit = prices[price_index+1] - prices[price_index]
                if new_profit > 0:
                    profit += new_profit
            return profit

        # Build the table
        buys = [float('-inf')]*k
        sells = [0]*k
        for price in prices:
            for transaction in range(k):
                if transaction == 0:
                    new_buy = -price
                else:
                    new_buy = sells[transaction-1] - price

                buys[transaction] = max(buys[transaction], new_buy)
                sells[transaction] = max(sells[transaction], buys[transaction] + price)
        return sells[k-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        // Corner cases 1: Usual
        if(prices.size() == 0 || k == 0)
            return 0;

        // Corner case 2: unlimited transactions
        if(k >= prices.size()/2) {
            int profit = 0;
            for(int priceIndex = 0; priceIndex < prices.size()-1; priceIndex++) {
                int newProfit = prices[priceIndex + 1] - prices[priceIndex];
                if(newProfit > 0)
                    profit += newProfit;
            }
            return profit;
        }

        // Build the table
        vector<int> buys(k, INT_MIN);
        vector<int> sells(k, 0);
        for(int price: prices) {
            for(int transaction = 0; transaction < k; transaction++) {
                int new_buy = -price;
                if(transaction != 0)
                    new_buy = sells[transaction - 1] - price;
                buys[transaction] = max(buys[transaction], new_buy);
                sells[transaction] = max(sells[transaction], buys[transaction] + price);
            }
        }
        return sells[k-1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    public int maxProfit(int k, int[] prices) {
        // Corner cases 1: Usual
        if(prices.length == 0 || k == 0)
            return 0;

        // Corner case 2: unlimited transactions
        if(k >= prices.length/2) {
            int profit = 0;
            for(int priceIndex = 0; priceIndex < prices.length - 1; priceIndex++) {
                int newProfit = prices[priceIndex+1] - prices[priceIndex];
                if(newProfit > 0)
                    profit += newProfit;
            }
            return profit;
        }

        // Build the table
        int[] buys = new int[k];
        for(int buyI = 0; buyI < k; buyI++)
            buys[buyI] = Integer.MIN_VALUE;

        int[] sells = new int[k];
        for(int sellI = 0; sellI < k; sellI++)
            sells[sellI] = 0;

        for(int price: prices) {
            for(int transaction = 0; transaction < k; transaction++) {
                int new_buy = -price;
                if(transaction != 0)
                    new_buy = sells[transaction - 1] - price;
                
                buys[transaction] = Math.max(buys[transaction], new_buy);
                sells[transaction] = Math.max(sells[transaction], buys[transaction] + price);
            }
        }
        return sells[k-1];
    }
}