Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A transaction may earn from either a price increase or a decrease, but only one position can be open at a time. Track whether we are flat, holding a normal position, or holding a short position, together with a completed-transaction count or allowance.

Approach

Python's dp[day][t][state] uses exactly t completed transactions. Impossible states start at negative infinity, and day zero allows a flat balance of zero, a normal position of -price, or a short position of +price only at t = 0. JavaScript initializes those three balances for every t, so its states instead mean at most t completed transactions.

Both versions use the same transitions. Carry each previous-day state forward. From a flat state, open a normal or short position at the same t. Close a normal position by adding today's price, or a short by subtracting it, reading a holding state at t - 1. Thus closure consumes one completed transaction or one unit of its allowance.

All transitions read only the previous day, preventing closure and reopening on the same day. Return the best final flat state over t up to k, excluding unfinished positions. Both state conventions therefore solve the required at-most-k problem.

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        n = len(prices)

        # dp[i][t][s] - s = not holding | holding normal | holding short
        dp = [[[-inf] * 3 for t in range(k + 1)] for i in range(n)]
        dp[0][0][0] = 0 # skip day
        dp[0][0][1] = -prices[0] # open normal
        dp[0][0][2] = prices[0] # open short

        for i in range(1, n):
            for t in range(k + 1):
                # no changes
                dp[i][t][0] = dp[i - 1][t][0]
                dp[i][t][1] = dp[i - 1][t][1]
                dp[i][t][2] = dp[i - 1][t][2]

                dp[i][t][1] = max(dp[i][t][1], dp[i - 1][t][0] - prices[i]) # open normal
                dp[i][t][2] = max(dp[i][t][2], dp[i - 1][t][0] + prices[i]) # open short

                if t:
                    dp[i][t][0] = max(dp[i][t][0], dp[i - 1][t - 1][1] + prices[i]) # close normal
                    dp[i][t][0] = max(dp[i][t][0], dp[i - 1][t - 1][2] - prices[i]) # close short
        
        return max(dp[-1][t][0] for t in range(k + 1))

Complexity analysis

Let n = prices.length. Time: O(n * k). Auxiliary space: O(n * k) for day/transaction/position DP states.