Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock IV

What is this problem about?

The "Best Time to Buy and Sell Stock IV interview question" is the generalized version of the transaction-limited stock problem. You are given an array of prices and an integer k. You may complete at most k transactions. This problem requires you to scale your logic from the 2-transaction version to an arbitrary number of transactions.

Why is this asked in interviews?

Tech giants like Google and Nvidia use the "Best Time to Buy and Sell Stock IV coding problem" to test a candidate's ability to generalize a solution. It involves a 2D DP table where one dimension is the day and the other is the number of transactions. It also includes an optimization edge case: if $k \geq n/2$, it becomes equivalent to Stock II (unlimited transactions).

Algorithmic pattern used

This problem follows the Dynamic Programming pattern with an optimization for large $k$.

1. Optimization: If $k$ is greater than or equal to half the number of days, you can make as many transactions as you want. Use the Stock II greedy algorithm ($O(N)$).
2. DP Table: dp[i][j] represents the maximum profit using at most i transactions up to day j.
3. Transition:
   • Either we don't trade on day j: dp[i][j] = dp[i][j-1]
   • Or we sell on day j: dp[i][j] = max(prices[j] + max_diff) where max_diff is the best dp[i-1][m] - prices[m] for all m < j. To keep it $O(NK)$, we update max_diff as we iterate through the days.

Example explanation

Prices: [3, 2, 6, 5, 0, 3], $k = 2$

• For $k=1$: Max profit is 4 (buy at 2, sell at 6).
• For $k=2$:
  • Transaction 1: buy at 2, sell at 6 (profit 4).
  • Transaction 2: buy at 0, sell at 3 (profit 3).
  • Total: 7. The DP table helps us keep track of the maximum possible profit at each number of allowed trades.

Common mistakes candidates make

• Memory Limit Exceeded: Using a $O(NK)$ table when $k$ is very large and not applying the Stock II optimization.
• $O(N^2 K)$ complexity: Using a triple loop to find the best previous buying day instead of maintaining a "running maximum difference."
• Off-by-one errors: Getting confused between the index of the transaction and the index of the day.

Interview preparation tip

Practice the transition from 1D DP to 2D DP. Many problems start with "at most 1" or "at most 2" and then ask for "at most K." Mastering the generalized version proves you understand the underlying "Dynamic Programming" mechanics.