Best Time to Buy and Sell Stock IV - Video Solutions

Problem Overview: You receive an array prices where prices[i] is the stock price on day i. You may complete at most k buy-sell transactions. Each transaction consists of buying once and selling once. The goal is to compute the maximum profit while respecting the transaction limit.

Approach 1: State-based Dynamic Programming (O(nk) time, O(nk) space)

This method models the problem using explicit DP states. Let dp[t][i] represent the maximum profit achievable using at most t transactions up to day i. For each day, you decide whether to skip trading or sell the stock, which requires tracking the best previous buy opportunity. While iterating through days, maintain a running value like maxDiff = max(dp[t-1][j] - prices[j]) to efficiently compute profits. The approach systematically fills the DP table and clearly illustrates the transaction transitions, making it useful for understanding the classic dynamic programming formulation.

Approach 2: Dynamic Programming with State Compression (O(nk) time, O(k) space)

The DP table can be compressed because each transaction state depends only on the previous transaction layer. Maintain two arrays: buy[t] and sell[t]. buy[t] tracks the best profit after buying for the t-th transaction, and sell[t] tracks the best profit after selling. Iterate through the prices array and update these states sequentially for each transaction count. This reduces memory from O(nk) to O(k) while preserving the same recurrence, making it the preferred implementation in production or interviews. The iteration simply processes each price and updates transaction states using constant-time transitions.

Approach 3: Greedy Optimization for Large k (O(n) time, O(1) space)

If k >= n/2, the constraint effectively disappears because you can perform unlimited transactions. In this case, the optimal strategy is to sum every positive price difference between consecutive days. Iterate once through the array and accumulate max(0, prices[i] - prices[i-1]). This converts the problem into the classic unlimited transaction variant from stock trading problems and avoids unnecessary array DP processing.

Recommended for interviews: Interviewers usually expect the dynamic programming formulation with transaction states. Explaining the full DP table shows understanding of the recurrence. Implementing the state-compressed version demonstrates stronger optimization skills and familiarity with advanced dynamic programming patterns.