Pattern visualizer
Buy and Sell Stock IV
Add a second dimension to the single-transaction DP: dp[t][d] is the best profit using at most t transactions through day d. Each day you either carry yesterday's value forward, or sell today against the cheapest effective buy price the (t-1)-transaction row has offered so far. Tracking that running best price as diff = max(dp[t-1][m] - prices[m]) turns an O(k*n^2) table into O(k*n), because diff only ever needs updating once per day, not re-scanned. Animated on: k = 2, prices = [3, 2, 6, 5, 0, 3] — with at most 2 buy-sell transactions, find the maximum achievable profit..
dp[t][d] = max(carry yesterday, sell today against the best transaction-(t-1) buy price so far)
dp[t][d] = max profit using at most t transactions through day d
dp[0][d] = 0 for every day: with zero transactions allowed, no profit is possible no matter which prices you see.
1FUNCTION maxProfitK(k, prices):2 n <- LENGTH(prices)3 dp <- (k+1) x n TABLE OF 04 FOR t FROM 1 TO k:5 diff <- dp[t-1][0] - prices[0]6 FOR d FROM 1 TO n-1:7 dp[t][d] <- MAX(dp[t][d-1], prices[d] + diff)8 diff <- MAX(diff, dp[t-1][d] - prices[d])9 RETURN dp[k][n-1]
← / → step · space play · Home restart