Best Time to Buy and Sell Stock with k Transactions: Dynamic Programming Explained
This is one of the most comprehensive stock trading problems you'll encounter in coding interviews. It generalizes simpler "buy and sell" problems by allowing up to k transactions — forcing you to use dynamic programming rather than a simple greedy pass. Mastering this problem builds deep intuition for DP state design, a skill that pays off across dozens of interview questions.
Why Dynamic Programming?
With k allowed transactions, there's no greedy rule that always works. You can't just grab every profitable day-to-day gain, because some gains might "use up" a transaction that could have earned more elsewhere. You need to track state: how many transactions have I used so far? That's the signature of a DP problem.
The Key Insight: Unlimited Transactions Shortcut
If k >= n // 2, you can make a transaction on every profitable pair of consecutive days — effectively unlimited. This shortcut avoids an expensive DP table for large k values:
# When k is very large, grab every upward move:
sum(max(prices[i] - prices[i-1], 0) for i in range(1, n))
DP State Design
Define dp[i][j] = maximum profit achievable using prices up to day i with at most j transactions completed.
The recurrence uses a rolling variable max_diff to avoid an inner O(n) loop, keeping the overall complexity at O(n*k):
max_difftracks the best "buy price adjusted for previous profit" seen so far.- At each day i: either hold (don't sell today) or sell today using the best prior buy.
Code Implementation
def maxProfit(k, prices):
if not prices or k == 0:
return 0
n = len(prices)
# Shortcut: if k >= n//2, unlimited transactions
if k >= n // 2:
return sum(max(prices[i] - prices[i - 1], 0) for i in range(1, n))
# dp[i][j] = max profit up to day i with at most j transactions
dp = [[0] * (k + 1) for _ in range(n)]
for j in range(1, k + 1):
max_diff = -prices[0] # best (dp[i][j-1] - prices[i]) seen so far
for i in range(1, n):
# Either skip today, or sell today with the best prior buy
dp[i][j] = max(dp[i - 1][j], prices[i] + max_diff)
# Update best buy point for next iteration
max_diff = max(max_diff, dp[i][j - 1] - prices[i])
return dp[-1][-1]
print(maxProfit(2, [2, 4, 1])) # 2 (buy day 1, sell day 2)
print(maxProfit(2, [3, 2, 6, 5, 0, 3])) # 7 (buy day 2 sell day 3, buy day 5 sell day 6)
print(maxProfit(0, [1, 2, 3])) # 0 (no transactions allowed)
print(maxProfit(2, [])) # 0 (empty prices)
Complexity Analysis
- Time: O(n * k) — two nested loops: n days × k transaction limits. The
max_difftrick eliminates a third inner loop. - Space: O(n * k) — the 2D DP table. Can be optimized to O(k) by keeping only two rows at a time.
Tracing Through Example 2
# prices = [3, 2, 6, 5, 0, 3], k = 2
#
# Transaction 1 (j=1):
# Day 1: sell at 2, best buy at 3 → max_diff = -3, dp[1][1] = max(0, 2-3) = 0
# Day 2: sell at 6 → dp[2][1] = max(0, 6-3) = 4
# ...
#
# Transaction 2 (j=2):
# Uses profit from transaction 1 as basis for next buy
# Best total: buy day 2 (price=2), sell day 3 (price=6) = +4
# buy day 5 (price=0), sell day 6 (price=3) = +3
# Total = 7
Edge Cases
assert maxProfit(2, []) == 0 # empty array
assert maxProfit(0, [1, 2, 3]) == 0 # k = 0, no transactions
assert maxProfit(2, [5]) == 0 # single day, can't complete a transaction
assert maxProfit(2, [5, 4, 3]) == 0 # strictly decreasing, never profitable
assert maxProfit(2, [1, 2]) == 1 # one transaction, one day profit
print("All edge cases passed!")
Key Takeaways
- When k ≥ n//2, use the unlimited-transactions greedy shortcut.
dp[i][j]= max profit by day i with ≤ j transactions; the recurrence tracks a runningmax_diffto stay O(n*k).- Time: O(n*k), Space: O(n*k) — reducible to O(k) with rolling arrays.
- Selling before buying again is enforced naturally by the DP structure.
What to Learn Next
You've now solved the most general stock trading problem. Revisit simpler variants to confirm you understand the progression: one transaction (single pass greedy), unlimited transactions (grab every upswing), at most 2 transactions (specific k=2 DP), and finally this k-transaction version. Then apply the same DP thinking to stock with cooldown and stock with transaction fee — two popular follow-up problems that add state to each day rather than to each transaction count.
