Max Profit with K Transactions [Python]

A great question that I recently did on AlgoExpert, its the kind of question that checks you on how well you understand the concepts on dynamic programming.

The question is given an array of prices of a single stock over multiple days, find the maximum profit you can generate in k transactions. You can only buy one stock and cannot buy again before you sell it.

input: prices -> [2, 5, 7, 3, 10], k -> 2
output: 12 (7 - 2 (transaction1) + 10 - 3(transaction2))

The first thought that came to my mind was to use the concept of peaks and valleys(buying when the prices are the lowest and selling just before the prices start dropping again) and then choose k transactions with the highest profit, this does not work. Let's take the example above:

k = 1
possible transaction (1)-> buy at 2 sells at 5
possible transaction (2)-> buy at 3 sells at 10

Here according to our strategy the answer would be 7 but looking at the array again we could buy at 2 and sell at 10. The strategy above forces us to buy at the local minima and sell at the maxima, we dont get the see the bigger picture.

Dynamic Programming

The problem looks like it could be solved using dynamic programming, but what do you store here, since the question is about max profit a good guess would be to store max profit up to a certain point but how does that help us and how would we go about it. This is why this question is very trick although it's extremely simple to code.

The array given to us is the price of the stock at day d. So we create a table with dimensions d * (k+1), transactions from 0 to k(inclusive). The idea is to keep track of maximum possible profit at day d in t transactions.

   2 5 7 3 10
   ----------
0| 0 0 0 0 0
1| 0 3 5 5 8
2| 0 3 5 5 12

On any particular day, we can decide to SELL or carry over previous maximum profit, meaning no transaction occurred. In other words we decide if selling now is a profit or loss and act accordingly.

Now when we decide to sell, how do we decide which day should we have brought the stock on, this is where our table becomes useful. When we sell we get selling price - buying price the profit in the current transaction, + maximum profit in previous transactions on the day we bought the stock. If we sell at day d, buy at day x and we have k transactions we get prices[d] - prices[x] + max_profit[t-1][x], we want to maximize max(max_profit[t-1][x]), x->[0, d-1] and then finally compare it to maximum profit in k transactions at d-1 day which is max_profit[t][d-1].

def maxProfitWithKTransactions(prices, k):
    # Time: O(kn) | Space: O(n)
    prev_trans = [0 for _ in prices]

    for t in range(k):
        curr_trans = [0]
        max_diff = float('-inf')

        for i in range(1, len(prices)):
            max_diff = max(max_diff, prev_trans[i-1] - prices[i-1])
            curr_trans.append(max(curr_trans[i-1], prices[i] + max_diff))
        prev_trans = curr_trans[:]

    return curr_trans[-1]